How to do the kSum in O(1), i only can do it like public long ksum(int k) { long sum = 0; for(int i=0; i
How to do the kSum in O(1), i only can do it like
public long ksum(int k) {
long sum = 0;
for(int i=0; i<k && i<ds.size(); i++)
sum += ds.get(ds.size() - 1 - i);
return sum;
}
The hint is
Consider the data stream: 1 2 3 4 5
Store this in a arraylist: [1,2,3,4,5]
Now have a cumulative sums arraylist:
data: [1
sums = [1
data: [1, 2
sums = [1, 3
data: [1,2,3
sums: [1, 3, 6
data: [1, 2, 3, 4
sums: [1, 3, 6, 10
data: [1, 2, 3, 4, 5]
sums: [1, 3, 6, 10, 15]
Now if in part1, calculate ksum(2):
sums list: [1, 3, 6, 10, 15]
ksum(2) = 9
If you can correctly identify which values at which particular indices you subtract to get ksum(2) = 9 in this case, you have a O(1) solution for ksum, since with each addition and removal of an element from the raw data arraylist, you add and remove from the sums arraylist as well
but i do not get it. Please give a code for example
Step by step
Solved in 3 steps with 1 images
