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"
