The latest in a series of paired-up problem workings with Greg Bowie. This week we’re looking at Problem 8:

Discover the largest product of five consecutive digits in a the

[provided]1000-digit number

Here’s my response, longhand:

- I’ll need a variable to store the (current) value of the greatest product
- I’ll need to iterate through the 1000-digit number, reading 5 digits at a time working out the product of each sequence, stepping one digit on with every iteration.
- The routine will begin from the 1st digit. The process will stop 5 digits of the final digit
- Using variables to store the length of the 1000-digit number and the number of digits we’re deriving the product of would make the solution more adaptable for other numbers and sequences
- Each product retrieved from every sequence of 5 digits must be compared to the current greatest product. If this exceeds the current greatest product, we set this as the new greatest product

This should solve the problem, but why stop now?

### Refinements

The presence of zeros in the 1000-digit number is notable – any zero encountered while examining the product of multiple digits will result in a zero product. So I’ll ignore them:

- Create an array of smaller numbers by splitting the 1000-digit number by any zero digit – handling sequences of zeros so as to prevent empty array items
- Iterate through each of these numbers, deriving the product of each set of 5 digits, and checking this against the current greatest product

Chances are this refinement will not improve the performance of this test on a single number, but as it reduces the number of product-derivation runs by 398 by it may scale well, depending on the language.

numDigits = ratherLongNumber.to_s.length

considerRange = 5

totalcomparisons = 0

$greatestProduct = 0

while totalcomparisons range = ratherLongNumber.to_s[totalcomparisons,5]

rangeproduct = range.split(//).map(&:to_i).inject(:*)

$greatestProduct = $greatestProduct>rangeproduct ? $greatestProduct:rangeproduct

totalcomparisons=totalcomparisons+1

end

puts "#{$greatestProduct}"

Refined version:

def getProductOfRange(inputNumber,considerRange)

# puts inputNumber

numberofcomparisons = 0

localGreatestRange = 0

while numberofcomparisons range = inputNumber.to_s[numberofcomparisons,5]

rangeproduct = range.split(//).map(&:to_i).inject(:*)

numberofcomparisons=numberofcomparisons+1

localGreatestRange = localGreatestRange>rangeproduct ? localGreatestRange:rangeproduct

end

return localGreatestRange ,numberofcomparisons

end

$greatestProduct = 0

arrayOfNumbers = ratherLongNumber.to_s.split(/0+/).map(&:to_i)

arrayOfNumbers.each{

|a|

tmp2,comparisons = getProductOfRange(a,5)

$greatestProduct = $greatestProduct>tmp2 ? $greatestProduct:tmp2

}

puts "#{$greatestProduct}"

here’s Greg’s response, posted simultaneously today.

update 23/01/2012:

Revisiting this afresh I realise there’re other ways to skip those pesky zeros, rather than drop them into an array, better to simply skip past any such sequence:

numDigits = ratherLongNumber.to_s.length

considerRange = 5

greatestProduct = 0

cursor = 0

skipped = 0

while cursor <= numDigits-considerRange

range = ratherLongNumber.to_s[cursor,considerRange]

if range.index('0')

cursor=(cursor+range.index('0'))+1

skipped=skipped+1

else

rangeproduct = range.split(//).map(&:to_i).inject(:*)

greatestProduct = greatestProduct>rangeproduct ? greatestProduct:rangeproduct

cursor=cursor+1

end

end

puts "Greatest Product: #{greatestProduct}"

puts "#{skipped} sequences with zero in the #{considerRange}-digit range skipped"

Excellent point about ’0′ – hadn’t even considered that. Did think the other way of only multipling when it contained a 9 but realised that wouldn’t be fool-proof.