CODEWITHSUNDEEP
c++calgorithmslidingsub-array
Enigma
Enigma

Reputation: 189

To find sum of all consecutive sub-array of length k in a given array

I want to find out all the sum of continuous sub-array of length K for a given array of Length n given that k < n. For example, let the given array be arr[6]={1,2,3,4,5,6} and k=3,then answer is (6,9,12,15). It can be obtained as :

(1+2+3)=6,
(2+3+4)=9,
(3+4+5)=12,
(4+5+6)=15.

I have tried this using sliding window of length k,but its time complexity is O(n).Is any solution which takes even less time such as O(log n).

Upvotes: 1

Views: 1672

Answers (2)

ilim
ilim

Reputation: 4547

Unless you know certain specific properties of the array (e.g. the ordering of the elements, the range of the elements included in the array, etc.) then you would need to check each individual value, resulting in an O(n) complexity.

If, for instance, you knew that the sum of the values in the array were T (perhaps because you knew T itself or were given the range) then you could consider that all the elements except the first and last (K-1) elements would be included in K different sums. This would mean a sum of T.K minus some amount, and you could reduce the values of the first and last K values appropriate amount of times, resulting in an algorithm of complexity O(K).

But note that, in order to achieve a strategy similar to this, you would have to know some other specific information regarding the values in the array, may that be their range or their sum.

Upvotes: 7

oybek
oybek

Reputation: 650

You can use Segment tree data structure, though building of it will take O(n log n), but than you can find sum of any interval in O( log n ), and modify each element of array in O( log n ) https://en.wikipedia.org/wiki/Segment_tree

Upvotes: 1

Related Questions