HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaModerate

Project Euler #8 code implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codeimplementationprojecteuler

Problem

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

Solution

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

Code Snippets

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);
    }
}
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);
    }
}
runningProduct /= temp.charAt(i - 13) - '0';

Context

StackExchange Code Review Q#101565, answer score: 12

Revisions (0)

No revisions yet.