CODEWITHSUNDEEP
algorithm
Cameron Cheung
Cameron Cheung

Reputation: 319

Finding best algorithm for sum of a section of an array's values

Given an array of n integers in the locations A[1], A[2], …, A[n], describe an O(n^2) time algorithm to compute the sum A[i] + A[i+1] + … + A[j] for all i, j, 1 ≤ i < j ≤ n.

I've tried multiple ways of solving this problem but none have in O(n^2) time.

So for an array containing {1,2,3,4} You would output:

1+2 = 3

1+2+3 = 6

1+2+3+4 = 10

2+3 = 5

2+3+4 = 9

3+4 = 7

The answer does not need to be in a specific language, pseudocode is preferred.

Upvotes: 1

Views: 1267

Answers (2)

vlad_tepesch
vlad_tepesch

Reputation: 6891

A good preperation is everything.

You could create an array of integrals:

I[0..n] = (0, I[0] + A[1], I[1] + A[2], ..., I[n-1]+A[n]);

This will cost you O(n) * O(1) (looping over all elements and doing one addition);

Now you can calculate each Sum(A, i, j) with just a single subtraction: I[j] - I[i-1]; so this has O(1)

Looping over all combinations of i and j with 1 <= (i,j) <= n has O(n^2).

So you end up with O(n) * O(1) + O(n^2) * O(1) = O(n^2) .

Edit:
Your array A starts at 1 - adapted to this - this also solves the little quirk with i-1 So the integral array I starts with index 0 and is 1 element larger than A

Edit:

Upvotes: 1

trincot
trincot

Reputation: 349946

First you'll maybe have thought about the most naive idea:

Naive idea

Create a function that for given values of i and of j will return the sum A[i] + ... + A[j].

function sumRange(A, i, j):
    sum = 0
    for k = i to j
        sum = sum + A[k]
    return sum

Then generate all pairs of i and j (with i < j) and call the above function for each pair:

for i = 1 to n
    for j = i+1 to n
        output sumRange(A, i, j)

This is not O(n²), because already the two loops on i and j represent O(n²) iterations, and then the function will perform yet another loop, making it O(n³).

Better idea

The above can be improved. Look at the repetition it performs. The sum that was calculated for given values of i and j could be reused to calculate the sum for when j has increased with 1, without starting from scratch and summing the values between i and (now) j-1 again, only to add that one more value to it.

We should just remember what the previous sum was, and add A[j] to it.

So without a separate function:

for i = 1 to n
    sum = A[i]
    for j = i+1 to n
        sum = sum + A[j]
        output sum

Note how the sum is not reset to 0 once it is output. It is preserved, so that when j is incremented, only one value needs to be added to it.

Now it is O(n²). Note also how it does not require an extra array for storage. It only needs the memory for a few variables (i, j, sum), so its space complexity is O(1).

As the number of sums you need to output is O(n²), there is no way to improve this time complexity any further.

NB: I assume here that single array values do not constitute a "sum". As you stated in your question, i < j, and also in your example you only showed sums of at least two array values. The above can be easily adapted to also include single value "sums" if ever that were needed.

Upvotes: 0

Related Questions