CODEWITHSUNDEEP
algorithmcomplexity-theory
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Find O(n) solution to variation of prefix sum

Problem

I know that this problem is a variation of prefix-sum, i'm just having some difficulty setting it up.

Upvotes: 3

Views: 131

Answers (4)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70949

The idea I propose boils down to what is already suggested in the other answers. However I want to propose an implementation with constant memory overhead:

initialize S with 0
for i = 2 to n {
  S[i] = S[i -1] + A[i - 1] // somewhat similar to prefix sum array
}

help = 0 // a single variable - constant memory overhead
for i = n to 1 {
  S[i] += help
  help += A[i]
}

After the first iteration S[i] stores the sum of all values with indices less than i. On the second iteration I add the sum of the values on the right of the current value.

Upvotes: 1

Sorin
Sorin

Reputation: 11968

Define B[i] = A[1] + ... A[i-1] and C[i] = A[i+1] + ... + A[n] then S[i] = B[i] + C[i].

You can compute both arrays in linear time. You need to iterate backwards to compute C in linear time.

Total number of additions is 3N - 2 (one addition for each position, expect the first in B and last in C).

Upvotes: 1

amit
amit

Reputation: 178471

Define:

P[i] = A[i+1] + A[i+2] + ... + A[n]
Q[i] = A[1] + ... + A[i-1]

Then, S[i] = P[i] + Q[i]

Upvotes: 2

ig-melnyk
ig-melnyk

Reputation: 2879

What about calculating two arrays: Lefts[i] which will be equal the sum of first i elements, :

Lefts[i] = A[0]+A[1]+A[2]..+A[i]

and Rights[i] which will be equal to the sum of the last i elements :

Rights[i] = A[n-1]+A[n-2]..+A[i]

Then S[i] = Left[i-1]+Rigt[i+1].

Upvotes: 2

Related Questions