Ahmed Mattar - 4 years ago 92

Java Question

so I'm solving a coding challenge and my code failed in test cases with large number of inputs due to timeout.

I need to do a simulation of "count" times.

each simulation will produce a random number between 0 and 364 of "size" times

each number should be stored and counted if two numbers are stored in the same index that mean the count is '2' then Hits++

return the percentage of hits with respect to "count"

`public double calculate(int size, int count) {`

// TODO -- add your code here

int Hits=0;

for(int j=1;j<=count;j++) { // number of simulation

int BirthDays[]=new int[365];

Random rnd = new Random();

rnd.setSeed(j);

for(int i=0;i<size;i++){ //number of people

int x=rnd.nextInt(365);

BirthDays[x]=BirthDays[x]+1;

if(BirthDays[x]>=2){

Hits++;

break;

}

}

}

return(((float)Hits/count)*100);

}

so is there any way to reduce the time complexity ?

the data structure can be changed it is not exclusive to arrays .

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

The biggest time saver I see immediately is to move `Random rnd = new Random()`

out of the loop. You don't need to create a new instance each time and it is quite slow.

```
public double calculate(int size, int count) {
int max = 365;
int birthDays[] = new int[max];
Random rnd = new Random();
int hits = 0;
for(int j = 1; j <= count; j++) {
Arrays.fill(birthDays, 0);
rnd.setSeed(j);
for(int i = 0; i < size; i++) {
int x = rnd.nextInt(max);
birthDays[x]++;
if(birthDays[x] >=2 ) {
hits++;
break;
}
}
}
return (hits/count) * 100;
}
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**