5
\$\begingroup\$

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....

|improve this question
\$\endgroup\$
  • \$\begingroup\$ i think it was pretty stupid of me to find minimum and then check for the minimum to be zero.... I could have simply checked for the zero directly... \$\endgroup\$ – Altamash Khan Aug 21 '15 at 14:32
12
\$\begingroup\$

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. :)

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ the idea of skipping that many numbers ahead was good..... and you really solved the '0' problem.... \$\endgroup\$ – Altamash Khan Aug 21 '15 at 15:04
  • \$\begingroup\$ @AltamashKhan Not a problem, you can also see it in action here. \$\endgroup\$ – Der Kommissar Aug 21 '15 at 15:09
  • \$\begingroup\$ Great implementation..... loved your code. \$\endgroup\$ – Altamash Khan Aug 21 '15 at 15:09
  • \$\begingroup\$ This is kind of a pedantic remark, but the OP's implementation is not \$O(n^2)\$, but \$O(13 n)\$, which is actually \$O(n)\$. Nice code, anyway! \$\endgroup\$ – Jaime Aug 21 '15 at 18:38
  • \$\begingroup\$ @Jaime I had a suspicion about that, I had asked someone to check on it but no one did. :( \$\endgroup\$ – Der Kommissar Aug 21 '15 at 19:08
7
\$\begingroup\$

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

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Yes.. i understand.. but then i had the problem with the zeroes..... so i got messed up.... \$\endgroup\$ – Altamash Khan Aug 21 '15 at 14:38
  • \$\begingroup\$ @AltamashKhan oh... I see... I didn't think of that \$\endgroup\$ – Tawcharowsky Aug 21 '15 at 14:38
  • 1
    \$\begingroup\$ While this is good advice generally, indeed there is a problem with zeros that has to be figured out. This is a step in the right direction though, now solve the zero problem :) \$\endgroup\$ – Simon Forsberg Aug 21 '15 at 14:40
  • \$\begingroup\$ can't we shorten the code by doing something with the 0's and the 1's .... i am just not good enough to come with a suitable algo... :/ \$\endgroup\$ – Altamash Khan Aug 21 '15 at 14:40
  • 1
    \$\begingroup\$ @AltamashKhan so what if the product of the firs five digits is -24... you are only interested in finding the maximum, so product that has 0 in it will probably not be the maximum unless there are zeros at every 13th place, in which case you will get negative number as the maximum product(using the forementioned algorithm). But that is the special case that you can handle while outputing the solution, if the max product is less than zero, max product iz zero. Good luck, have fun implementing :) \$\endgroup\$ – Tawcharowsky Aug 21 '15 at 15:02
4
\$\begingroup\$

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);
    }
}
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ yes i commented that..... ... i realized that "min" is useless.... \$\endgroup\$ – Altamash Khan Aug 21 '15 at 14:58

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.