Ahmed Mattar Ahmed Mattar - 4 years ago 92
Java Question

Is there any way to avoid nested "for" loops in java

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 .

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