1
\$\begingroup\$

Project Euler Problem 8 asks:

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Is there any better way to make my code more efficient? How can I make the class and method names shorter?

 public class LargestProductSeries {
private String largeNum =
        "73167176531330624919225119674426574742355349194934" +
                "96983520312774506326239578318016984801869478851843" +
                "85861560789112949495459501737958331952853208805511" +
                "12540698747158523863050715693290963295227443043557" +
                "66896648950445244523161731856403098711121722383113" +
                "62229893423380308135336276614282806444486645238749" +
                "30358907296290491560440772390713810515859307960866" +
                "70172427121883998797908792274921901699720888093776" +
                "65727333001053367881220235421809751254540594752243" +
                "52584907711670556013604839586446706324415722155397" +
                "53697817977846174064955149290862569321978468622482" +
                "83972241375657056057490261407972968652414535100474" +
                "82166370484403199890008895243450658541227588666881" +
                "16427171479924442928230863465674813919123162824586" +
                "17866458359124566529476545682848912883142607690042" +
                "24219022671055626321111109370544217506941658960408" +
                "07198403850962455444362981230987879927244284909188" +
                "84580156166097919133875499200524063689912560717606" +
                "05886116467109405077541002256983155200055935729725" +
                "71636269561882670428252483600823257530420752963450";



 public LargestProductSeries() {
        computeProduct();
    }

    private void computeProduct() {
        int limit = 13;
        long sum = 1;
        long previousSum = 0;
        int[] x = new int[15];

        for (int i = 0; i < largeNum.length(); i++, limit++) {
            if (limit > largeNum.length()) {
                break;
            }
            for (int j = i, k = 0; j < limit; j++, k++) {
                x[k] = Integer.parseInt(String.valueOf(largeNum.charAt(j)));

                sum = x[k] * sum;

            }

            if (sum < previousSum) {
                sum = previousSum;

            }
            previousSum = sum;
            System.out.println("Largest sum: " + sum);

            sum = 1;

        }

    }

}
\$\endgroup\$
  • \$\begingroup\$ @WorBlux Comments are for clarifying the question. Please write all advice in answers instead. \$\endgroup\$ – 200_success Jun 8 '16 at 23:35
  • \$\begingroup\$ Didn't feel it was worth it without specific code, but since you asked so nicely... Had to do a "not a robot" check to make it post though. \$\endgroup\$ – WorBlux Jun 9 '16 at 0:46
5
\$\begingroup\$

Let's go through it step-by-step.

for (int j = i, k = 0; j < limit; j++, k++) {
    x[k] = Integer.parseInt(String.valueOf(largeNum.charAt(j)));

    sum = x[k] * sum;

}

In this for loop, whose goal is to calculate the product of the limit digits starting at the index i, there are multiple concerns:

  • You are converting the character at the index j to an integer by first turning it into a String and parsing that String into an integer. You can do it in a more direct manner by using Character.getNumericValue(char); this will directly return the numeric value of the character, i.e. 5 for the character '5'. Also, since we know before-hand that we will be dealing with digits that are only [0-9] (and not all Unicode digits), we can even use a simple arithmetic calculation with largeNum.charAt(j) - '0'.
  • You are using a pre-allocated array to store this integer. You don't need it: you can just store the integer as a local variable. This will also simplify the for loop conditions: it is currently iterating over both a j and a k when only one is really needed.

With those considerations, you could have:

for (int j = i; j < limit; j++) {
    int digit = largeNum.charAt(j) - '0';
    sum *= digit;  // which is the same as "sum = digit * sum"
}
if (sum < previousSum) {
    sum = previousSum;

}
previousSum = sum;

This works but is awkward to read: we're interested in getting the maximum sum and this code is dealing with a "sum" and a "previous sum". Also, why are talking about "sum" when the problem deals with "products"?

Consider renaming the result to maximumProduct and the current product to product. With this, you can have:

maximumProduct = Math.max(maximumProduct, product);

which is a lot clearer: at the end of calculating the product for the current index, we retrieve the maximum of the current maximum and the calculated product, using Math.max.

sum = 1;

The first remark is: what is this code doing at the end of the for loop? It actually initializes a value for sum that will be used for the product of the next index. Thus, this should be placed at the top of the loop: let the current index initialize its temporary values correctly.

if (limit > largeNum.length()) {
    break;
}

It took me a bit of time to figure out why this code was there. Its purpose is actually to "correct" the fact that the subsequent loop considers limit digits because its ending condition is

//                  v---v
for (int j = i; j < limit; j++) {

You should not change the value of limit. This in fact a constant of the problem: it is the number of consecutive digits to consider. Thus, what you need to do is:

  • At index i, consider the next limit digits with

    for (int j = i; j < i + limit; j++)
    //                  ^-------^
    
  • End the main loop when there are less than limit digits left with

    for (int i = 0; i < largeNum.length() - limit; i++)
    //                  ^-----------------------^
    

Additional comments

  • As said before, limit is a constant of this problem. At the very least, it should be given as parameter of computeProduct, just like largeNum. Both of those could then be made constants (i.e. private static final).
  • computeProduct, despite its name, does more than computing the product; it actually prints it. Consider changing the method so that it returns the wanted product. Then, you can have the main method print it.

All in all, this is what you end up with:

private long computeProduct(int limit, String largeNum) {
    long maximumProduct = 1;
    for (int i = 0; i < largeNum.length() - limit; i++) {
        long product = 1;
        for (int j = i; j < i + limit; j++) {
            int digit = largeNum.charAt(j) - '0';
            product *= digit;
        }
        maximumProduct = Math.max(maximumProduct, product);
    }
    return maximumProduct;
}
\$\endgroup\$
  • \$\begingroup\$ if limit and largeNum is constant should I also change its name to all capitalise? \$\endgroup\$ – Emmaaaaaaa Jun 9 '16 at 2:12
  • 1
    \$\begingroup\$ @EmmaAutumn The constant themselves can be written in all caps yes. The parameters of computeProduct (int limit, String largeNum) still remain camelCase. \$\endgroup\$ – Tunaki Jun 9 '16 at 7:39
1
\$\begingroup\$

Within the for (int j = i, k = 0; j < limit; j++, k++) loop you should assign sum to zero and break whenever x[k] is zero as continuing through the loop is pointless (the product of zero and anything is zero).

Bonus points if you can assign i=j so the for loop it's nested in doesn't waste time with a bunch of sums that will also turn out to be zero

\$\endgroup\$
1
\$\begingroup\$

If performance is a concern, avoiding math will save you some cycles. In Tunaki's example, an extra subtraction/addition is computed every time the for loop's condition is tested, and it performs 13 multiply operations every time through. It should only need 12, and even then only if all the digits are non-zero.

public void findMaxProduct(int limit, String testString) {
    int maxStart = largeNum.length() - limit - 1;
    long maxProduct = 0;
    int maxProductStart = 0;

    for (int i = 0; i < maxStart; i++) {
        long product = computeProduct(largeNum.substring(i, i + limit).getBytes());
        if (product > maxProduct) {
            maxProduct = product;
            maxProductStart = i;
        }
    }

    System.out.println("Max product: " + maxProduct);
    System.out.println("Starting index: " + maxProductStart);
}

private long computeProduct(byte[] digits) {
    int length = digits.length;
    long product = digits[0];
    for (int i = 1; i < length && product != 0; i++) {
        product *= digitValue(digits[i]);
    }
    return product;
}

private int digitValue(byte value) {
    return value - '0';
}
\$\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.