N次迭代後數組中所有元素的和

Question

給定數組arr [] = {4,6,8,3,6}數組中所有元素的和= 27。現在，讓我們對陣列： -

對於所有的i <長度（ARR）-1，ARR [I] = ARR [I] -arr第[i + 1]

所以，現在該陣列變成{-2，-2， 5，-3}，數組的所有元素之和= -2

我們再次執行相同的操作，數組變爲{0,7，-8}，數組的所有元素之和= 1

因此，我們看到： -

第0次迭代後，arr [] = {4,6,8,3,6}。數組中所有元素的和= 27

第一次迭代後，arr [] = { - 2，-2,5，-3}。數組中所有元素的和= -2

第二次迭代後，arr [] = {0，-7,8}。數組中所有元素的和= 1

第3次迭代後，arr [] = {7，-15}。數組中所有元素的和= -8

給定一個整數N，問題是確定第N次迭代後數組的所有元素之和。

我已經成功地嘗試了蠻力的方法，顯然它的時間複雜度是二次的。如果可能的話，我正在尋找具有更好的時間複雜性的方法，最好是線性的。

Answer 1

一次迭代後的數組元素的總和爲：

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

所以問題歸結爲尋找最後和陣列的N-1次迭代後的第一個元素。

我們有：

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] 

一種模式：所述第一元件是總和（-1）^ķ C（N，k）的一個[K]，其中k會從0到N. （C（n，k）是binomial coefficient）

如果你有一個計算二項式係數的O（1）算法，你可以在線性時間內計算N-1次迭代後列表的第一個和最後一個元素， N次迭代後的列表總和就是它們之間的差異。