5
\$\begingroup\$

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

public class SmallestMultiple {

    public static void main(String[] args) {
        int smallest = 0;

        for(int num = 2; num < 1000000000; num += 2) {
            boolean isMultiple = true;

            for (int multiple = 1; multiple <= 20; multiple++) {

                if (num % multiple != 0) {
                    isMultiple = false;
                }
            }

            if (isMultiple == true) {
                smallest = num;
                break;
            }
        }

        System.out.println(smallest);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Also, should I delete my question once I find a satisfying answer? I don't want to spoil it for others. \$\endgroup\$ – Ethan Watson Jul 8 '16 at 2:14
  • 6
    \$\begingroup\$ No, you should not delete a question after receiving such an answer. \$\endgroup\$ – Jamal Jul 8 '16 at 2:25
  • \$\begingroup\$ What are you expecting to get out of this code review ? \$\endgroup\$ – user633183 Jul 8 '16 at 2:35
  • \$\begingroup\$ I'm trying to write better code with stack overflow's help. Results so far are positive. If you look at my previous questions, similar responses are a great indicator. \$\endgroup\$ – Ethan Watson Jul 8 '16 at 2:39
  • \$\begingroup\$ The algorithm can be much reduced by taking a step back and thinking about the problem at hand. See this previous answer of mine. \$\endgroup\$ – Phylogenesis Jul 8 '16 at 10:58
13
\$\begingroup\$
                if (num % multiple != 0) {
                    isMultiple = false;
                }

I got a five times speed improvement simply by adding a break; to this.

                if (num % multiple != 0) {
                    isMultiple = false;
                    break;
                }

Now it doesn't keep checking 4, etc. after failing on 3.

        for(int num = 2; num < 1000000000; num += 2) {

Why 2? If you're going with this kind of speedup, go ahead and use what you know.

        for (int num = 2520; num < 1000000000; num += 2520) {

And if you do that, change

            for (int multiple = 1; multiple <= 20; multiple++) {

to

            for (int factorCandidate = 11; factorCandidate <= 20; factorCandidate++) {

I changed the incorrect multiple to factorCandidate because I found multiple confusing. It wasn't a multiple of anything. It was a candidate to be one of the factors of the number. Another alternative would be to simply call it i, which at least is not misleading about what it does (if a bit uninformative).

This works because you already know that it's divisible by the first ten (your original could have started at 3 for the same reason, since all numbers are divisible by 1 and you only checked even numbers).

If we start at 2520 and increment only by multiples of 2520, then we maintain the property that it is divisible by all of the first ten numbers. If we would instead add one, then we would lose that property. The most obvious example is that we would no longer be divisible by 2, as the even number would become odd. But in fact, we wouldn't be divisible by any of the first ten numbers except 1. Similarly, 27,720 (11*2520) is the least common multiple of 1 to 11. All greater multiples are multiples of it.

The combination of those two changes speeds up the algorithm by almost a thousand times.

But that suggests a new algorithm. Rather than iterating to find the Least Common Multiple (LCM) of 1 to 20 directly, why not find the LCM of 1 to 11 and use that to get the LCM of 1 to 12, etc.?

       int smallest = 0;

        for(int num = 2; num < 1000000000; num += 2) {
            boolean isMultiple = true;

            for (int multiple = 1; multiple <= 20; multiple++) {

                if (num % multiple != 0) {
                    isMultiple = false;
                }
            }

            if (isMultiple == true) {
                smallest = num;
                break;
            }
        }

So replace all of this with

        int smallest = 2520;

        for (int nextFactor = 11; nextFactor <= 20; nextFactor++) {
            for (int previous = smallest; smallest % nextFactor != 0; smallest += previous) ;
        }

That gives another hundred times speedup. This solution is actually faster than the mathematical solution using the greatest common divisor (GCD) to determine the LCM. At least for the range 1 to 20.

        int smallest = 2520;

        for (int nextFactor = 11; nextFactor <= n; nextFactor++) {
            smallest *= nextFactor / gcd(nextFactor, smallest);
        }

Note that this works by the same principles that justified incrementing by 2520 earlier.

Of course, the fastest runtime solution is just

        int smallest = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19;

The compiler will go ahead and calculate that for you. That's just the largest multiple of each prime that appears in the range 1 to 20. Note that only 2 and 3 get higher multiples than just themselves. This is because 5 * 5 is greater than 20 as are all integer powers of larger primes.

You can implement this more generally with a sieve.

        int [] divisors = new int[20];

        for (int i = 0; i < divisors.length; i++) {
            divisors[i] = i + 1;
        }

        for (int i = 1; i < divisors.length; i++) {
            for (int j = i + 1; j < divisors.length; j++) {
                if (divisors[j] % divisors[i] == 0) {
                    divisors[j] /= divisors[i];
                }
            }
        }

        int smallest = divisors[0];
        for (int i = 1; i < divisors.length; i++) {
            smallest *= divisors[i];
        }

But of course, it isn't as fast that way. We can write out the same result manually:

        int smallest = 1 * 2 * 3 * 2 * 5 * 1 * 7 * 2 * 3 * 1;
        smallest *= 11 * 1 * 13 * 1 * 1 * 2 * 17 * 1 * 19 * 1;

But I find it easier to read without the ones and with like divisors grouped (as 16, 9, etc.).

Using the sieve this way allows us to avoid explicitly calculating which numbers are prime, which are powers, and which are composites with multiple prime factors (the ones). We sieve out extra factors directly.

The sieve is relatively fast, but not as much so as the GCD solution or the simple increment by the previous LCM solution.

\$\endgroup\$
  • \$\begingroup\$ The num += 2520 part of the line for (int num = 2520; num < 1000000000; num += 2520) might require more explanation. The OP showed insight by only searching even numbers but there is still quite a leap between understanding divisibility by 2 and divisibility in general. Regardless, nice answer. \$\endgroup\$ – twohundredping Jul 8 '16 at 6:51
  • \$\begingroup\$ Yes, please explain the num += 2520. Great answer by the way. \$\endgroup\$ – Ethan Watson Jul 8 '16 at 14:38
4
\$\begingroup\$

Hello I can help by giving clues.

a) The biggest box is 20, therefore the least significant digit will always be 0 for the smallest possible output.

b) Numbers 1..10 will not be required because they are factors of 11..20.

c) For each number from 11..19, Every even number requires an occurrence of 5 times in order to have a least significant digit 0. Every odd number requires an occurrence of 10 times in order to have a least significant digit 0.

Visual:
11 every 10
12 every 5
13 every 10
14 every 5
15 every 10
16 every 5
17 every 10
18 every 5
19 every 10
20 every 1

By using these clues even with brute force it will decrease the computation time. However the clue is also leading towards a non-brute force solution.

The philosophy is also workable in dynamic inputs, not just numbers ranging 1..10, or 1..20 etc. That is why I did not suggest 2520 per hop.

Good luck!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.