2
\$\begingroup\$

This method finds the smallest positive number that is evenly divisible by all numbers from 1 to 20.

I am wondering if there is a better way to test if all iterations of a for loop completed successfully. When I put the found boolean outside the for loop, it was terminating my while loop prematurely since the break in the for loop goes to the end and executes whatever is below the for loop inside the while loop. It also seems a bit sloppy to subtract the number that is given and then add 1 to it inside the while loop. But if I put the number++ below the for loop after found is set true and I don't need to increment the number anymore. It increments one last time.

For example, for the number 20, the answer is 232792560. But due to the last increment it would return 232792561, which is an incorrect answer.

public int getLowestDiv(int n) {    
    //initialize found variable, as we havent found the number yet
    boolean found = false;
    /* initilize the number as what was passed to this method minus 1, since we will increment below*/
    int number = n - 1;

    while (found != true) {
        number++;

        for (int i = 1; i <= n; i++) {
            //for 1 to int that was passed divide the current number and see if its divisible
            if (number % i != 0) {
                break;
            } else if (i == n)
                found = true;
        }
    }
    return number; 
}

I have looked through the specs for Java's loops and didn't find anything about handling these type of situations. Specifically, I will loop for a certain number of iterations, testing if something is true, and if not, break, but only execute a particular statement if the for loop passed the condition on all iterations. I would like to see what the status-quo is when it comes to this as I've run into it before.

\$\endgroup\$
5
\$\begingroup\$

There are two parts to my initial assessment of your code.

Firstly, often the 'best' way to solve a problem where you are tempted to have a found = true type situation is to call a seperate method for that part of the work, and to simply 'return value' when you find the value... for example, your code:

     for (int i = 1; i <= n; i++) {
         //for 1 to int that was passed divide the current number and see if its divisible
            if (number % i != 0) {
             break;

         } else if (i == n)
             found = true;

     }

would be easily written as:

private static final boolean checkValue(final int value, int n) {
    while (n > 1) {
        if (value % n != 0) {
            return false;
        }
        n--;
    }
    return true;
}

then your main loop becomes:

int number = n;

while (!checkValue(number, n)) {
     number++;
}
System.out.printf("Number %d is divisible by all positive values up to %d\n", number, n);

The second issue I have is for performance..... you should not be using number++, you will save a lot of time if you only check the multiples of the largest number, so:

number += n; // instead of number++;

EDIT

If you look at the math, you will see that, we can do much better than number += n, and can determine that if we find a value that is a multiple of both n and n - 1 that the final result will be a multiple of that value. If we can use that value as the 'step' then we will go faster than just using n. Similarly, if we can find a multiple of all n, n - 1, and n - 2 then that would be a good step too.

So, consider the following:

private static final int checkValue(final long value, int n) {
    while (n > 1) {
        if (value % n != 0) {
            return n;
        }
        n--;
    }
    return 1;
}

This loop now returns the value at which the expression fails....

and we can use that in our main loop as follows:

    final int n = 23;

    long number = n;

    long step = n;
    int fact = n;
    int bestfact = fac;
    while (number > 0 && (fact = checkValue(number, n)) > 1) {
        if (bestfac > fact) {
            bestfac = fact;
            step = number;
        }
        number += step;
    }

    if (number < 0) {
        System.out.println("No values were found (overflow) divisible by all " + n + " factors");
    }

On my computer, the difference between this optimization and a naieve step, is 0.022ms vs 4961.271ms (or 225000 times faster!!!!!!!)

\$\endgroup\$
  • \$\begingroup\$ I should add, that I tested the code with n = 23 and it overflows. I recommend adding while (number > 0 && !checkValue(number, n)) {...} as a check on the loop, and only report success if number > 0 (i.e. no overflow). If you convert number to a long, then it get a solution for 23 at 5354228880 \$\endgroup\$ – rolfl Nov 19 '13 at 18:12
  • 2
    \$\begingroup\$ I am a sucker for performance problems, so I thought I would update you with a change to the algorithm which makes it much faster...... see my edit: \$\endgroup\$ – rolfl Nov 19 '13 at 18:20
  • 2
    \$\begingroup\$ It wasn't mentioned, but looping from n downwards gives a performance increase, since things are less likely to be divisible by 20 or 19 than by 2 or 3. Also, a completely different approach using the prime factorization of everything < n would let you calculate the result directly (this would replace the code with something else entirely, though). \$\endgroup\$ – Michael Shaw Nov 19 '13 at 18:29

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.