Sum of all elements of an array after N iterations

Question

Given an Array arr[ ]={4,6,8,3,6} sum of all elements of the array = 27. Now, let us perform an operation on the array:-

For all i < length(arr)-1, arr[i]=arr[i]-arr[i+1]

So now the array becomes {-2,-2,5,-3}, sum of all elements of the array = -2

We perform the same operation again, the array becomes {0,7,-8}, sum of all elements of the array = 1

Thus, we see:-

After 0th iteration, arr[ ]={4,6,8,3,6}. Sum of all elements of the array = 27

After 1st iteration, arr[ ]={-2,-2,5,-3}. Sum of all elements of the array = -2

After 2nd iteration, arr[ ]={0,-7,8}. Sum of all elements of the array = 1

After 3rd iteration, arr[ ]={7,-15}. Sum of all elements of the array = -8

Given an integer N, The question is to determine the sum of all the elements of the array after Nth iteration.

I have successfully tried the Brute Force approach and obviously it's time complexity is quadratic. I am looking for an approach with a better time complexity preferably linear, if possible.

Answer 1

After one iteration the sum of the elements of the array is:

a[0]-a[1] + a[1]-a[2] + ... + a[n-1]-a[n] = a[0] - a[n]

So the problem is reduced to finding the last and the first element of the array after N-1 iterations.

We have:

N       First element
1       a[0]-a[1]
2       a[0]-a[1]-(a[1]-a[2])              = a[0]-2a[1]+a[2]
3       a[0]-2a[1]+a[2]-(a[1]-2a[2]+a[3])  = a[0]-3a[1]+3a[2]-a[3]

A pattern emerges: the first element is the sum of (-1)^k C(N,k) a[k] with k going from 0 to N. (C(n,k) being the binomial coefficient)

If you have an O(1) algorithm for calculating binomial coefficients you can calculate the first and last elements of the list after N-1 iterations in linear time, and the sum of the list after N iterations is just the difference of those.