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

Project Euler - Problem 8

More about Project Euler.

Problem description

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




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