Recover the array (Editorial)

Solution

We can reverse the prefix-sum process in order to get the original array , this can be done using difference array , so the new reversed process will be :

• consider an initial element x=a_1.

• a_1 remains the same.

• consider difference array $d$ of d_1,d_2,..,d_{n-1}

• go through all i=2,..,n then d_i \gets a_i-a_{i-1}

• a \gets [a_1,d_1,d_2,..,d_{n-1}]

The process will be repeated exactly $k$ times , and then the original array $a$ is restored.

Complexity $O(nk)$

def solve():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    for _ in range(k):
        d=[]
        for i in range(1,n):
            d.append(a[i]-a[i-1])
        a=[a[0]]+d
    print(*a)

for _ in range(int(input())):
    solve()