Project Euler : Problem 8 - Largest product in a series

Problem Statement : Largest product in a series

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

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

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

Concept and Theory

One can solve this as a $2-Pointer \ Technique$. One pointer being $startPosition$ and other pointer being $currentPosition$. Then we just need to consider following algorithm :

1. If current number = $0$ then increment $currentPosition$ and set $startPosition = currentPosition$ , since including $0$ in our product will make the product $0$ only, thats why just move both the pointer to the $currentPosition$.
2. If the difference between $currentPosition$ and $startPosition$ is less than or equal to the given length, then
3. if less than given length just increment $currentPosition$ and calculate $currentProduct$ using the number at current position.
4. if equal to the given length do the same and check if the $currentProduct$ is greater than $maxProduct$ and update if it is.
5. If the difference between $currentPosition$ and $startPosition$ is greater than given length, then simply multiply the number at $currentPosition$ and divide by the number at $startPosition$. After that increment both $startPosition$ and $currentPosition$ and check if the $currentProduct$ is greater than $maxProduct$ and update if it is.

Code

/**
 * A function that takes a string of numbers and returns the largest product of
 * k consecutive terms in that number
 *
 * @param num
 *            : number as a string
 *
 * @param nDigitNumber
 *            : length of the number string
 *
 * @param kConsecutiveNumbers
 *            : length of the consecutive terms whose product needs to be
 *            maximized
 *
 * @return largest possible product
 */
public static long largestProduct(String num, int nDigitNumber, int kConsecutiveNumbers) {
  char numArray[] = num.toCharArray();
  long currentProduct = 1;
  long maxProduct = 0;

  int startPosition = 0;
  int currentPosition = 0;

  while (currentPosition < nDigitNumber) {
    if (numArray[currentPosition] == '0') {
      currentProduct = 1;
      currentPosition++;
      startPosition = currentPosition;
    } else if (currentPosition - startPosition <= kConsecutiveNumbers - 1) {
      currentProduct *= (numArray[currentPosition] - '0');
      if (currentPosition - startPosition == kConsecutiveNumbers - 1 && maxProduct < currentProduct) {
        maxProduct = currentProduct;
      }
      currentPosition++;
    } else {
      currentProduct *= (numArray[currentPosition] - '0');
      currentProduct /= (numArray[startPosition] - '0');
      currentPosition++;
      startPosition++;
      if (maxProduct < currentProduct) {
        maxProduct = currentProduct;
      }
    }
  }

  return maxProduct;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as given in the above mentioned post, $largestProduct$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler