I am trying to find all numbers between 1 and 10000000 (both inclusive). I tried two solutions
But, the loop approach is taking smaller time than the 'Divide & Conquer approach' (10 times lesser approximately). I searched for the solutions online as well. But, I could find loop approach only. Is there something I am missing in my approach which is increasing my execution time? Please point me to that. I started from a List, moved to Sorted Set, then finally settled to use HashSet, but seems to take time.
Here is what I tried.
`
public static void main(String[] args) {
System.out.println("Numbers divisible by 3 and 5:");
nosDivisibleBy3And5(); // divide & conquer approach (approach to consider)
nosDivisibleBy3And5BruteForce();
}
private static void nosDivisibleBy3And5BruteForce() {
IntStream ar = IntStream.range(1, 10000001); // start inclusive, end exclusive
Integer[] array = ar.boxed().toArray(Integer[]::new);
List<Integer> list = new ArrayList<>();
int count = 0;
long start = System.currentTimeMillis();
/*
* Traversing array from 1 to 100,
* if it is either divisible by 3 or 5 or both, count it , print it.
*
*/
for(int i = 0; i < array.length ; i ++) {
if((array[i] % 3 == 0) || (array[i] % 5 == 0)) {
//System.out.println(array[i]);
list.add(array[i]);
count++;
}
}
long end = System.currentTimeMillis();
System.out.println("Brute Force Approach:");
System.out.println("No of elements counted: " + count);
//Collections.sort(list);
//System.out.println("Elements: " + list);
System.out.println("Time: " + (end - start));
}
private static void nosDivisibleBy3And5() {
/*
* Set has all those numbers which
* are divisible by both 3 and 5.
*
*/
Set<Integer> elementsSet = new HashSet<Integer>();
int fr3,
fr5,
mid,
count;
fr3 = 2; // fr3 indicates the index of the first value divisible by 3.
fr5 = 4; // fr5 indicates the index of the first value divisible by 5.
count = 0;
int end3 = 9999998 , // end3 indicates the index of the last value divisible by 3.
end5 = 9999999; // end5 indicates the index of the last value divisible by 5.
/* Getting all the numbers from 1 to 100 from Intstream object */
IntStream ar = IntStream.range(1, 10000001); // start inclusive, end exclusive
Integer[] array = ar.boxed().toArray(Integer[]::new);
/*
* Using divide and conquer approach , mid divides the array from 1 to 100
* in two parts, on the first fr3 and fr5 will work, on the second part end3
* and end5 will work.
*/
mid = (fr3 + end3)/2;
long start = System.currentTimeMillis();
while(fr3 <= mid && end3 >= mid) {
elementsSet.add(array[fr3]);
elementsSet.add(array[fr5]);
elementsSet.add(array[end3]);
elementsSet.add(array[end5]);
fr3 += 3;
fr5 += 5;
end3 -= 3;
end5 -= 5;
}
long end = System.currentTimeMillis();
System.out.println("Our approach");
System.out.println("No of elements counted: " + elementsSet.size());
//System.out.println("Elements:" + elementsSet);
System.out.println("Time: " + (end - start));
}
}
`
Here is another solution, partially based on the excellent answer by DelfikPro.
It simplifies the logic for calculating the array size, but adds more code to prevent the need for using the relatively slow % remainder operator, and eliminates the need to iterate over numbers that don't go into the result array.
As such, it should execute faster, though I haven't benchmarked to see if it actually does.
static int[] multiplesOfThreeAndFive(int from, int to) { // both inclusive
int count = ((to / 3) - ((from - 1) / 3)) // how many divisible by 3
+ ((to / 5) - ((from - 1) / 5)) // how many divisible by 5
- ((to / 15) - ((from - 1) / 15)); // how many divisible by 15, counted twice above
int[] result = new int[count];
int[] multiples = { 0, 3, 5, 6, 9, 10, 12 };
int startIndex = Arrays.binarySearch(multiples, from % 15);
if (startIndex < 0)
startIndex = -startIndex - 1;
for (int r = 0, offset = from / 15 * 15; r < count; offset += 15, startIndex = 0)
for (int i = startIndex; r < count && i < multiples.length; i++, r++)
result[r] = offset + multiples[i];
return result;
}
Tests
System.out.println(Arrays.toString(multiplesOfThreeAndFive(1, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(0, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(29, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(30, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(31, 99)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(31, 101)));
Outputs
[3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]
[0, 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99]
[30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]
[30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]
[33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99]
[33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]