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

第 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) ^k C(N,k) a[k] 的总和，其中 k 从 0 到 N。（C(n,k) 是二项式系数）

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