N 반복 후 배열의 모든 요소의 합

Question

배열의 모든 요소의 arr [] = {4,6,8,3,6} 합계가 27 인 경우를 가정 해 봅시다. 어레이 - 모든 내용

I < 길이 (도착) -1,3- 도착 [I] =의 도착 [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 번째 반복 이후에 배열의 모든 원소의 합을 결정하는 것이 중요합니다.

나는 Brute Force 접근법을 성공적으로 시도했으며 분명히 시간 복잡성은 2 차입니다. 나는 가능하다면 직선적으로 더 좋은 시간 복잡성을 가진 접근법을 찾고있다.

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) ^{0 N.가는 K와 K} C (N, K)는 [K] (C (n, k)가 binomial coefficient 인 경우)

이항 계수를 계산하는 알고리즘이 O (1)이면 선형 시간의 N-1 회 반복 후 목록의 첫 번째 요소와 마지막 요소를 계산할 수 있습니다. N 회 반복 후리스트의 합은 그것들의 차이 일뿐입니다.