Largest Product I

Given a long string of digits, find four sequential single digits with the largest product. See string below for example (line breaks for clarity).

533057076358665178794023266942242568372779820617762395757
339121317065191716131926992412240221012678039931631871966
926992412240221905798323423378923688587988127275189678764

function getProduct(str, start, numCount) {
  let n = str[start]

  for (let i = 1; i < numCount; i++) {
    n = n * str[start + i]
  }

  return n
}

function getMax(str, numCount) {
  let max = 0
  let start = 0

  for (let i = 0; i < str.length -1 - numCount; i++) {
    let n = getProduct(str, i, numCount)

    if (n > max) {
      max = n
      start = i
    }
  }
  return { max, start }
}

Each digit is visited 4 times except the first and last 3 digits of the string. So for a string of n digits, that is about O(4n) = O(n).

Scroll to top