Сумма всех элементов массива после N итераций

Question

Учитывая сумму Array arr [] = {4,6,8,3,6} суммы всех элементов массива = 27. Теперь давайте проведем операцию на массив: -

Для всех я < длина (обр) -1, обр [я] = обр [I] -arr [+ 1]

Итак, теперь массив становится {-2, -2, 5, -3}, сумма всех элементов массива = -2

Мы снова выполняем ту же операцию, массив становится {0,7, -8}, сумма всех элементов массива = 1

Таким образом, мы видим:

После 0-й итерации arr [] = {4,6,8,3,6}. Сумма всех элементов массива = 27

После 1-й итерации arr [] = {- 2, -2,5, -3}. Сумма всех элементов массива = -2

После 2-й итерации arr [] = {0, -7,8}. Сумма всех элементов массива = 1

После третьей итерации arr [] = {7, -15}. Сумма всех элементов массива = -8

Учитывая целое число N, вопрос заключается в определении суммы всех элементов массива после N-й итерации.

Я успешно пробовал подход Brute Force, и, очевидно, его временная сложность квадратична. Я ищу подход с лучшей временной сложностью, желательно, если это возможно, линейно.

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) ^к С (N, K) [к] с к идущей от 0 до N. (C (n, k) является binomial coefficient)

Если у вас есть алгоритм O (1) для вычисления биномиальных коэффициентов, вы можете вычислить первый и последний элементы списка после N-1 итераций в линейном времени, а сумма списка после N итераций - это просто разница.