CODEWITHSUNDEEP
javanumbers
Hiti3
Hiti3

Reputation: 172

How to find numbers that are dividable with 2, 3 or 5 in max 1 second

I need your help guys with this specific question.

How many numbers from an interval a <= b [1, 10^18] are dividable by 2, 3 or 5?

Result must be run in max 1 sec!

A standard program would use a for loop seen bellow.

a = 1;
b = 1000000000
results = 0;

for (int i = a; i <= b; i++){
    if (i % 2 == 0 || i % 3 == 0, i % 5 == 0){
        results++;
    }
}
System.out.println(results);

But if I enter high numbers, my program need a lot of time to give me the results.

Example 1:

a = 11, b = 30, result = 14

Example 2:

a = 123456789012345678, b = 876543210987654321 , result = 552263376115226339

Upvotes: 0

Views: 139

Answers (1)

kaos
kaos

Reputation: 1608

I came up with something like that

public static void main(String[] args) {
    long a = 123456789012345678L, b = 876543210987654321L;

    long start = System.currentTimeMillis();

    long score = getCount(b) - getCount(a - 1);

    System.out.println("Time: " + ((System.currentTimeMillis() - start)));
    System.out.println("Divisible by 2 or 3 or 5: " + score);
}

public static long getCount(long end) {
    return (end / 2) + (end / 3) + (end / 5) - ((end / 6)  + (end / 10) + (end / 15)) + (end / 30);
}

The solution:

  • It counts how many numbers are divisible by 2 or 3 or 5 separately and sums that.
  • Now we need to discard numbers that where counted twice: for 2 and 3 it will be every 6th number, for 2 and 5 every 10th number, for 3 and 5 every 15th number
  • At the end we need to include numbers that are divisible by 2 and 3 and 5 that where discarded in step 2 so we add every 30th number.

Upvotes: 1

Related Questions