arrays - N次迭代后数组所有元素的总和

Question

给定一个数组 arr[ ]={4,6,8,3,6} 数组所有元素的总和 = 27。现在，让我们对数组执行一个操作:-

对于所有 i < length(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

第三次迭代后，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)k C(N,k) a[k] 的总和，其中 k 从 0 到 N。(C(n,k) 是 binomial coefficient )

如果你有一个 O(1) 算法来计算二项式系数，你可以在线性时间内计算 N-1 次迭代后列表的第一个和最后一个元素，N 次迭代后列表的总和就是它们的差。