We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #8: Largest product in a series
Project Euler #8: Largest product in a series
Sort by
recency
|
212 Discussions
|
Please Login in order to post a comment
If you have test cases from 5 to 9 (both inclusively) failing, it means that is: (i) a memory scaling issue (where the first comment of this thread applies), (ii) probably performing unnecessary computations, (iii) missing a necesary computation.
Two things helped me for these, besides treating each digit individually to solve (i): (a) Use a sliding window approach. Compute the first window (0 to k - 1) once and move the window progressively. This is faster
O(n)
than the naïve approachO(n*k)
. (b) Track the amount of zeros with a counter. Update the zero count if a zero leaves or enters the window and act accordingly with the product. This should solve all the remaining test cases (which are for large k and n)https://github.com/Achintha444/projecteuler-_javascript/blob/main/8-euler008.js
answer in JS
Okay. I'm improving. This should have taken me atleast an hour. Done it in 20 mins. C# solution
JavaScript solution:
All test cases passed:
def Solve_Prob(n,k,strm): maxi = -1 for i in range(0,n-k+1): pro = 1 for j in range(i,i+k): pro = pro*int(strm[j]) if pro > maxi: maxi = pro answer = maxi return answer
t = int(input()) for i in range(0,t): n,k = list(map(int,input().split())) m = input() answer = Solve_Prob(n,k,m) print(answer)