Print the array after K operations

Easy
0/40
Average time to solve is 15m
28 upvotes
Asked in companies
Wells FargoCodenation

Problem statement

You are given an array 'ARR' consisting of 'N' integers and a non-negative integer 'K'. Consider an operation on the array as replacing every element 'ELE' of the array with 'MX - ELE', where 'MX' is the maximum element of the array. You need to return the updated array, given that this operation is performed on the array exactly 'K' number of times.

Note:

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
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.
Output Format: 
For each test case, print single space-separated integers denoting the array elements after 'K' operations.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 10^4
-10^9 <= ARR[i] <= 10^9
0 <= K <= 10^9

Time Limit: 1sec
Sample Input 1:
1
4 2
20 15 10 5
Sample Output 1:
15 10 5 0
Explanation for Sample Input 1:
The given array’s 0-based indexing is as follows:

In the first operation, maximum = 20.

20    15    10    5     
↓      ↓    ↓     ↓
0      5    10    15

These will be the array values, after one operation.

In the second operation,  maximum = 15.

0      5     10    15     
↓      ↓      ↓     ↓
15     10     5     0

Now the array to be returned is {15, 10, 5, 0}.
Sample Input 2:
1
4 3
0 0 9 18
Sample Output 2:
18 18 9 0
Approaches (1)
Simulation, Observation.
  • 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:
  1. Let's assume that the maximum element in the original array is ‘MAXM’.
  2. The given array is {'ARR'[0], ‘ARR’[1], …. ‘ARR’[x], … ‘ARR’[n-1]}.
  3. Let's assume ‘ARR[x]' is the maximum element in the current array.
  4. 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.
  5. 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.
  6. 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:
  1. 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.
  2. 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.
Time Complexity

O(N), where N is the size of the array.

 

Here, since we are traversing all the elements in the array given to us once which O(N), therefore the complexity here grows by the order O(N).

Space Complexity

O(1), as we are using constant extra memory.

Code Solution
(100% EXP penalty)
Print the array after K operations
Full screen
Console