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;}

## Birthday Chocolate

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

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!!