Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 21 Nov, 2020

Easy

```
1. The array follows 0-based indexing.
2. Note that after each operation, the next operation will be performed on the updated array i.e the array obtained after the last operation.
```

```
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains two integers 'N' and 'K', denoting the size of the array and the number of times operation is to be performed respectively.
The second line of each test case contains N space-separated integers denoting the array elements.
```

```
For each test case, print single space-separated integers denoting the array elements after 'K' operations.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N <= 10^4
-10^9 <= ARR[i] <= 10^9
0 <= K <= 10^9
Time Limit: 1sec
```

- If ‘K’ = 0, then no operations are performed on the array. So, in this case, simply return the original array.
- We know that in each operation, we are subtracting the array elements with the maximum value in the array, so we can be sure that after one operation, we will have 0 as at least one of the elements in the array and the rest of the elements will always be +ve.
- The array values after a single operation will become fixed and will change their order of occurrence as no of operations performed on the array increase.
- We can use this analogy to recognise their pattern of occurrence:

- Let's assume that the maximum element in the original array is ‘MAXM’.
- The given array is {'ARR'[0], ‘ARR’[1], …. ‘ARR’[x], … ‘ARR’[n-1]}.
- Let's assume ‘ARR[x]' is the maximum element in the current array.
- After applying one operation, the maximum number will be the one, whose difference with the current array element is maximum. In other words, operation ‘MAXIMUM’-'ARR[i]' will be maximum in the next array for an element that is minimum in the current array.
- After first step our array will be {'ARR[x]'-'ARR[0]', ‘ARR[x]’-'ARR'[1], ….0, ...'ARR[x]'-'ARR[n-1]'}, maximum element in this array will be at that index, at which minimum element was present in original array. Let's suppose that ‘ARR[1]’ was the minimum element in the original array.
- In our current array, the maximum element will be ‘MAXM’-'ARR[1]' and minimum element will be 0. After applying operation our array values will become: {'ARR[x]'-'ARR[1]'-'ARR[0]', 0, ….. ‘ARR[x]’-'ARR[1]' (at 0’s place in previous step), … ‘ARR[x]’-'ARR[1]'-'ARR[n-1]'}. Now, after two operations, maximum element = ‘ARR[x]’-'ARR[1]' and minimum element = 0.

- For example, in sample test 1, after one operation array becomes {0, 5, 10, 15}, after the second operation, the order of elements in the array changes to {15, 10, 5, 0}.
- After the third operation, the array again changes to {0, 5, 10, 15}, and so on till required operations.
- Thus, in conclusion, after trying similar simulations on other tests we can say that:

- If the asked number of operations ‘K’ is odd, then array elements will change to ‘ARR[i]’ - ‘MINIMUM’, where the minimum is the minimum element in the given array.
- If the asked number of operations ‘K’ is even, then array elements will change to ‘MAXIMUM’ - ‘ARR[i]’, where ‘ARR[i]’ is the maximum element in the given array.

Similar problems

Longest Subarray With Zero Sum

Moderate

Posted: 3 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023