Project Euler #8 code implementation

Question

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product." eg, the product of the first four adjacent digits is 7 * 3 * 1 * 6 = 126

public class Java {



public static void main(String[] args) {
    String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    long max = 0;
    for(int i = 0 ; i < temp.length()-12 ; i++){
        int min = temp.charAt(i)-48;
        long product = 1;
        for(int k = i ; k < 13+i ; k++){
            min =  Math.min(temp.charAt(k) - 48 , min);
            if( min == 0)
                {product = 0;
                break;}
            else {
                product = product*(temp.charAt(k)-48);
            }
        }

             if(product > max){
                 max = product;
             }




    }
     System.out.println("max : " + max);

    }
}

The code works perfectly and runtime is around 925323ns.

I had realized after posting that finding the minimum was useless... so forgive me for that....

Answer 1

The first thing you should do is clean your code up.

We should notice that temp.charAt(k)-48 is called no less than once, and no more than twice in the for (int k...) loop. We can fix that (quite easily).

Next, we should notice that if we find a 0 in our second loop, we can skip that many numbers ahead.

Lastly, aChar - 48 is bad practice. In Java you can subtract single-character literals. Instead of aChar - 48, let's do aChar - '0'. The 48 becomes a magic number, and it's just as easy to subtract the '0' instead. :)

public class Java {
    public static void main(String[] args) {
        String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        long max = 0;

        for (int i = 0; i < temp.length() - 12; i++) {
            int min = temp.charAt(i) - '0';
            long product = 1;

            for (int k = i; k < 13 + i; k++) {
                int numK = temp.charAt(k) - '0';
                min =  Math.min(numK, min);

                if (min == 0) {
                    product = 0;
                    i = k + 1; // The value at `k` is a zero, so we'll not bother processing from `i through k`.
                    break;
                }
                else {
                    product = product * numK;
                }
            }

            if (product > max) {
                max = product;
            }
        }

        System.out.println("max : " + max);
    }
}

---

Or, of course, rewrite the entire thing to one loop instead, which would be the preferred method.

public class Java {
    public static void main(String[] args) {
        String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        long max = 0;
        long runningProduct = 1;
        int numbersLoaded = 0;
        for (int i = 0; i < temp.length(); i++) {
            int numI = temp.charAt(i) - '0';

            if (numI == 0) {
                runningProduct = 1;
                numbersLoaded = 0;
            }
            else {
                if (numbersLoaded == 13) {
                    runningProduct /= temp.charAt(i - 13) - '0';
                }
                else {
                    numbersLoaded += 1;
                }

                runningProduct *= numI;

                if (runningProduct > max) {
                    max = runningProduct;
                }
            }
        }

        System.out.println("max : " + max);
    }
}

I will warn you, if taken out of context the following line is dangerous:

runningProduct /= temp.charAt(i - 13) - '0';

This could definitely cause a division by 0 error if not handled properly. (It's handled properly here, but could easily be made not to be.)

Here's a link to ideone with the two tests, for comparison.

All-in-all, I hope this was helpful. :)

Answer 2

Let's examine the first five adjecent digits, they are

7 * 3 * 1 * 6 * 7 = 882

and if you now compare it to the second five adjecent digits:

3 * 1 * 6 * 7 * 1 = 126

From that we can easily see that we can get the solution for the second equation if we devide the solution of the first equation by the first number(7) and multiply that with the next number (in this case 1).

Same logic can be applied to the 13 digit product.

What I'm saying is... you don't need nested loops.

EDIT: sorry... forgot about the "zero problem"

I just thought of something... why not replace all ocurences of 0 with -1, would that help? I didn't think this one throuhg, but this is basicaly what I had in mind: 0 is problematic only when we try to devide with it.

Let's see on an example: let's say we have the input:

0 1 2 3 4 5

then

0 * 1 * 2 * 3 * 4 = 0

if we replace the 0 with -1 we get

-1 * 1 * 2 * 3 * 4 = -24

the product of the next five digits is:

1 * 2 * 3 * 4 * 5 = 120

which is equal (-24 / -1) * 5

as we can see... division with -1 is not problematic

Answer 3

Why not call that string huge_number? Temp makes no sense here. The min code is confusing and unnecessary, just use if(temp.charAt(k)-48==0) break; So your revised code would look something like this:

public class Java {
public static void main(String[] args) {
    String huge_number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    long max = 0;
    for(int i = 0 ; i < huge_number.length()-12 ; i++){
        long product = 1;
        for(int k = i ; k < 13+i ; k++){
            if(huge_number.charAt(k-48) == 0){
                product = 0;
                break;
            }
            else {
                product = product*(huge_number.charAt(k)-48);
            }
        }
             if(product > max){
                 max = product;
             }
    }
     System.out.println("max : " + max);
    }
}