Find all multiples of 3 & 5 between two limits - Complexity

Question

I am trying to find all numbers between 1 and 10000000 (both inclusive). I tried two solutions

1. Brute Force Approach: Loop over all the numbers from 1 to 10000000, and find all which are divisible by either 3 or 5 or both.
2. Divide & Conquer approach: Having 4 counters (2 from start and 2 from end). 2 counters work on multiples of 3 and two work on multiples of 5. I am putting all multiples in a Set (I do not need Sorted elements, I only need elements , sorting increases my complexity as well).

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));
}

}

`

Answer 1

If returning a List<Integer> is the goal, you could have a O(1) time and space solution by extending AbstractList and implementing an iterator() that keeps track of the index of the next number, and implement get(int index), size(), equals(), hashCode() etc and iterator’s methods all by calculation based on the max number.

The List would be immutable (simply wrap using Collections. unmodifiableList()), but would fulfil the contract of List.

All done without actually storing any of the numbers.

Answer 2

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]

Answer 3

HashSet takes a lot of time on hashing and checking if element already exists and is slower than bare ArrayList's add()

If your problem is really finding all the numbers that are divisible by 3 or 5, than you could use array with predetermined length:

int from = 1;
int to = 1000000;
int d3 = (to / 3) - (from / 3) + (from % 3 == 0 ? 1 : 0); // how many divisible by 3
int d5 = (to / 5) - (from / 5) + (from % 5 == 0 ? 1 : 0); // how many divisible by 5
int d15 = (to / 15) - (from / 15) + (from % 15 == 0 ? 1 : 0); // how many divisible by 15

int[] array = new int[d3 + d5 - d15]; // counted 15's twice

int offset = 0;
for (int i = from; i <= to; i++) {
  if (i % 3 == 0 || i % 5 == 0) array[offset++] = i;
}