4
\$\begingroup\$

Question:

For a 1000-digit number, find the 13 adjacent digits which gives out the largest product.

My code goes like this:

series = '731...752963450' # the 1000 digit, simplified here. 

# Set up variables.
adjacent_count = 13
pointer = 0
candidates = [], products_array = []
pointer_end = series.length - (adjacent_count - 1)

# Get all candidates
begin
    candidates <<  series[pointer..pointer + adjacent_count - 1]
    pointer += 1
end while pointer < pointer_end

# Eliminate All candidates with 0s
candidates = candidates.map {|s| s.include?('0') ? nil : s}.compact

# do the multiplication and compare
candidates.each_with_index do |s, index|
    char_array = s.chars 
    product = 1
    char_array.each do |int|
        product = product * int.to_i
    end 
    products_array[index] = product
end

answer = products_array.max
equation = candidates[products_array.each_with_index.max[1]].chars * 'x'

puts "Maximum product from this series of digits is #{equation} = #{answer}"

Well I don't know whether I need to eliminate the candidates that contains zeroes in it or just directly go multiply all of those. Not sure if it will save up time using map method first, Any thoughts?

And for the last bit I tried to print out which candidate brings up this largest product so I created another array to store it. It seems it can be done in a more elegant way. Any thoughts?

\$\endgroup\$
4
\$\begingroup\$

The easiest way to think of this problem is to use a k-character sized window that slides across the number.

  • First calculate the product of the first k characters
  • Check to see if the next digit is 0, if it is, keep going until you hit a non-zero element and restart the process from that digit
  • If the next digit is not 0, then multiply the existing product by that digit and divide by the first digit of the existing product (the number that is going to be dropped off the window)

Keep track of the best sequence found and its product and you have your answer

The beauty of this approach is you only ever look at/multiply an element exactly once, giving O(n) time (where n is the length of the string). Your approach may multiply the same number k times (where k is the length of the window), resulting in O(kn) time, which is quite a bit slower.

\$\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.