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.

@tpacker Thanks. I appreciate your response.
Can you please help me understand how can we get O(n)
I couldn't figure out what makes it O(n^2) any leads would really be appreciated :)

So, your answer is not really O(n^2), but rather O(n*m), since your sum() method iterates over m elements in the array for every n element in the array. Thus, O(m*n).

You can improve though, if you figure out a smarter way to keep track of the sum of the m previous pieces.
You can for example just hold a sum variable where you remove the last element and add the new one as you iterate, instead of calculating the whole sum each and every time. (Imagine the repeated work when your m grows).

Here is a java example:

staticintsolve(intn,int[]s,intd,intm){intsum=0;intr=0;for(inti=0;i<s.length;i++){sum+=s[i];// M is never less than 1if(i>m-1)sum-=s[i-m];if(i>=m-1&&sum==d)r++;}returnr;}

Im not sure of this solution. This will not be working with this input:

51213332

The output should be 2 but will be 3 because it will count last digit of the series 3. This solution does not consider what if solution will be shorter than a month digit.

Sure, this will pass all validators but still... :).

This method wouldn't work if the numbers were not close together? I tested it for an array with suiting numbers in the opposite side of the array and sure enough it didn't work.

So, is there a way to find the anwer for this case?

## Birthday Chocolate

You are viewing a single comment's thread. Return to all comments →

This function uses a sliding window too :) If any corrections please comment :)

I believe this is O(n^2). O(n) is also possible.

@tpacker Thanks. I appreciate your response. Can you please help me understand how can we get O(n) I couldn't figure out what makes it O(n^2) any leads would really be appreciated :)

So, your answer is not really O(n^2), but rather O(n*m), since your sum() method iterates over m elements in the array for every n element in the array. Thus, O(m*n).

You can improve though, if you figure out a smarter way to keep track of the sum of the m previous pieces. You can for example just hold a sum variable where you remove the last element and add the new one as you iterate, instead of calculating the whole sum each and every time. (Imagine the repeated work when your m grows).

Here is a java example:

this is gold! thank you :)

m <= n, so O(nm) is

technicallyO(n^2) too, but O(nm) is a tighter upper bound.wow

Awesome solution. Some out of the box thinking there!!

Really great answer! out of the box.

Nice solution!!

yeah!!

Why is that it doesn't through list index out of range error?

The shortest method for the above python code

return sum(1 for x in range(len(s)) if sum(s[x:x+m]) == d)

Well done!

Im not sure of this solution. This will not be working with this input:

The output should be

`2`

but will be`3`

because it will count last digit of the series`3`

. This solution does not consider what if solution will be shorter than a month digit.Sure, this will pass all validators but still... :).

return sum(1 for x in range(len(s)) if sum(s[x:x+m]) == d and len(s[x:x+m]) == m )

That't beutiful thank you for sharing : i did this way but we can make way shorter by yours..

List comprehension is amazing

I agree but also his method is n * m time complexity sadly.

a minor optimization:

return sum(1 for x in range(len(s)-m+1) if sum(s[x:x+m]) == d)

can u explain wht this "1" is doing in sum( "1" for x in range(len(s)-m+1)

This method wouldn't work if the numbers were not close together? I tested it for an array with suiting numbers in the opposite side of the array and sure enough it didn't work.

So, is there a way to find the anwer for this case?

This is brilliant!. Please can you shed an insight as to why you used the index range i:m+i in line 5?

There is no need to check last M items in array S. Minor optimisation, but still: range(0, n - m + 1)

Hey I made this version of sliding windows in Python3... with O(n):

Such a Good solution bro.. I was working with left and right pointers and was stuck, but the "if i >= m-1" move is really good one.

is it work??