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.
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;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Subarray Division
You are viewing a single comment's thread. Return to all comments →
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: