K times, following operation is done on a array A1,A2…AN:
Choose maximum from array A, say MAX. Do Ai=MAX-Ai, for every 1 ≤ i ≤ N.
Print the final array.
0 ≤ K ≤ 109
1 ≤ N ≤ 105
There will a cycle of size not greater than 2. After that we can easily simulate the operations.
We can prove that there wouldn’t be cycle of size greater than 2 (proof is left as an exercise to reader). Means, that states of array will repeat after a maximum of 2 operations.
if k==0: print Array A return if k%2==1: k=1 else: k=2 for i=1 to k: mx=A for j=1 to N-1: mx=max(mx,A[j]) for j=0 to N-1: A[j]=mx-A[j] print array A.