You are on the Home/Other Tutorials/Project Euler/Problem 8 page

Project Euler - Problem 8

Problem description

Find the greatest product of five consecutive digits in the 1000-digit number.

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

Solution

Given the nature of the problem, the only obvious approach is to go through all the digits in the number. Start with the first digit in the number and create a set of 5 numbers from digits 1 through 5. Compute the product. Next, select the digits 2 through 6. Compare this product with the previous resutlt and retain the larger one. Move through all the digits until we get to the last sequence with the digits at positions 996, 997, 998, 999, and 1000.

There are some optimizations one can consider but I would look at them only if the performance of the "full enumeration" code is not acceptable. The two changes I can think of are

(1) if we detect a zero in our set of 5 digits, we can skip ahead to a sequence starting with the first digit after the zero.

(2) once we have a product for the first 5 numbers, to calculate the product for the next 5 digits, we should divide the last result by the number we just dropped from consideration and multiply by the new number. This way we use 1 division and 1 multiplication rather than 4 multiplications. I don't know if this would improve performance or not since we are trading one division for 3 multiplications.

It may be possible to find a solution "by inspection" but I don't know if this is a generalizable solution. In this specific scenario, since we can compare our answer with the correct solution available from the Project Euler website it might be possible to location a pattern of 2 or more 9's with some 8s and 7s thrown in. But, if we did not have a way to compare our guesses with the known maximum, I am not sure if this approach would be reliable.

Below is the VBA code to step through all possible sequences. I use the Debug.Assert to verify that I did not lose some digits in copying the large number from the webpage into the VBE. I also generalize the code somewhat by putting the length of the sequence of interest in a constant. Since the performance was very quick, I skipped the improvements mentioned above. Finally, I used Debug.Print rather than MsgBox so that I could copy the result and paste it into the Project Euler webpage for verification.

Sub Euler8()
    Dim Nbr As String
    Nbr = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843" _
        & "858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113" _
        & "622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776" _
        & "657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482" _
        & "839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586" _
        & "178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188" _
        & "845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
    Debug.Assert Len(Nbr) = 1000
    Dim I As Integer, Rslt As Long
    Const NbrChars As Integer = 5
    For I = 1 To Len(Nbr) - NbrChars + 1 Step 1
        Dim J As Integer, TempRslt As Long
        TempRslt = 1
        For J = 1 To NbrChars
            TempRslt = TempRslt * CInt(Mid(Nbr, I + J - 1, 1))
            Next J
        If TempRslt > Rslt Then Rslt = TempRslt
        Next I
    Debug.Print Rslt
    End Sub