Find final Array after subtracting maximum from all elements K times
Given an array arr[] of N integers and an integer K, the task is to do the below operations with this array K times. Operations are as follows:
- Find the maximum element (say M) from the array.
- Now replace every element with M-arri. where 1 ≤ i ≤ N.
Examples:
Input: N = 6, K = 3, arr[] = {5, 38, 4, 96, 103, 41}
Output: 98 65 99 7 0 62
Explanation:
1st operation => Maximum array element is 103. Subtract 103 from all elements. arr[] = {98, 65, 99, 7, 0, 62}.
2nd operation => Maximum array element is 99. Subtract 99 from all elements. arr[] = {1, 34, 0, 92, 99, 37}
3rd operation => Maximum array element is 99. Subtract 99 from all elements. arr[] = {98, 65, 99, 7, 0, 62}.
This will be the last state.Input: N = 5, K = 1, arr[] = {8, 4, 3, 10, 15}
Output: 7 11 12 5 0
Naive Approach: Simple approach is to perform the above operations K times. Every time find the maximum element in the array and then update all the elements with the difference from the maximum.
Time complexity: O(N*K).
Auxiliary Space: O(1).
Efficient Approach: The efficient solution to this problem is based on the below observation:
If K is odd then the final answer will be equivalent to the answer after applying the operation only one time and if K is even then the final array will be equivalent to the array after applying operations only two time.
This can be proved by as per the following:
Say maximum = M, and initial array is arr[].
After the operations are performed 1st time:
=> The maximum element of arr[] becomes 0.
=> All other elements are M – arr[i].
=> Say the new array is a1[]. So, a1[i] = M – arr[i].After the operation are performed 2nd time:
=> Say maximum of a1[] is M1.
=> The maximum element of a1[] becomes 0.
=> All other elements are M1 – a1[i].
=> Say the new array is a2[]. So, a2[i] = M1 – a1[i].
=> Maximum of a2[] will be M1, because the 0 present in a1[] changes to M1 and all other elements are less than M1.After the operation are performed 3rd time:
=> The maximum is M1.
=> The maximum changes to 0.
=> All other elements are M1 – a2[i] = M1 – (M1 – a1[i]) = a1[i].
=> So the new array is same as a1[].After the operation are performed 4th time:
=> Say maximum of the array is M1.
=> The maximum element changes to be 0.
=> All other elements are M1 – a1[i].
=> So the new array is the same as a2[]From the above it is clear that the alternate states of the array are same.
Follow the below steps to implement the observation:
- Take one variable max and store the maximum element of arr.
- If K is odd
- Traverse the array and subtract every element from the maximum element.
- Else
- Traverse the arr and subtract every element from the maximum element and
store the maximum element in max1 variable. - Again traverse the arr and subtract every element from the maximum element.
- Traverse the arr and subtract every element from the maximum element and
- Print the final array.
Below is the implementation of the above approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; // Function for converting the array void find( int n, int k, int arr[]) { // Find the maximum element in array int max = INT_MIN; for ( int i = 0; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // If k is odd if (k % 2 != 0) { for ( int i = 0; i < n; i++) { cout << max - arr[i] << " " ; } } // If k is even else { // Subtract the max from every // element of array and store // the next maximum element in max1 int max1 = INT_MIN; for ( int i = 0; i < n; i++) { arr[i] = max - arr[i]; if (arr[i] > max1) { max1 = arr[i]; } } // Print the output for ( int i = 0; i < n; i++) { cout << max1 - arr[i] << " " ; } } } // Driver code int main() { int N = 6, K = 3; int arr[] = { 5, 38, 4, 96, 103, 41 }; // Function call find(N, K, arr); return 0; } |
C
// C code for the approach #include <stdio.h> #include<limits.h> // Function for converting the array void find( int n, int k, int arr[]) { // Find the maximum element in array int max = INT_MIN; for ( int i = 0; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // If k is odd if (k % 2 != 0) { for ( int i = 0; i < n; i++) { printf ( "%d " , max - arr[i]); } } // If k is even else { // Subtract the max from every // element of array and store // the next maximum element in max1 int max1 = INT_MIN; for ( int i = 0; i < n; i++) { arr[i] = max - arr[i]; if (arr[i] > max1) { max1 = arr[i]; } } // Print the output for ( int i = 0; i < n; i++) { printf ( "%d " , max1 - arr[i]); } } } // Driver code void main() { int N = 6, K = 3; int arr[] = { 5, 38, 4, 96, 103, 41 }; // Function call find(N, K, arr); } // This code is contributed by ashishsingh13122000. |
Java
// Java code for the approach import java.io.*; class GFG { // Function for converting the array public static void find( int n, int k, int arr[]) { // Find the maximum element in array int max = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // If k is odd if (k % 2 != 0 ) { for ( int i = 0 ; i < n; i++) { System.out.print((max - arr[i]) + " " ); } } // If k is even else { // Subtract the max from every // element of array and store // the next maximum element in max1 int max1 = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { arr[i] = max - arr[i]; if (arr[i] > max1) { max1 = arr[i]; } } // Print the output for ( int i = 0 ; i < n; i++) { System.out.print((max1 - arr[i]) + " " ); } } } // Driver Code public static void main(String[] args) { int N = 6 , K = 3 ; int arr[] = { 5 , 38 , 4 , 96 , 103 , 41 }; // Function call find(N, K, arr); } } // This code is contributed by Rohit Pradhan |
Python3
# Python code # Function for converting the array def find(n, k, arr): # Find the maximum element in array max = ( - 2147483647 - 1 ) for i in range ( 0 , n): if (arr[i] > max ): max = arr[i] # If k is odd if (k % 2 ! = 0 ): for i in range ( 0 , n): print ( max - arr[i], end = " " ) # If k is even else : max1 = INT_MIN for i in range ( 0 ,n): arr[i] = max - arr[i] if (arr[i] > max1): max1 = arr[i] # Print the output for i in range ( 0 ,n): print (max1 - arr[i],end = " " ) # Driver code N = 6 K = 3 arr = [ 5 , 38 , 4 , 96 , 103 , 41 ] # Function call find(N,K,arr) # This code is contributed by ashishsingh13122000. |
C#
// C# code for the approach using System; class GFG { // Function for converting the array static void find( int n, int k, int []arr) { // Find the maximum element in array int max = Int32.MinValue; for ( int i = 0; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // If k is odd if (k % 2 != 0) { for ( int i = 0; i < n; i++) { Console.Write((max - arr[i]) + " " ); } } // If k is even else { // Subtract the max from every // element of array and store // the next maximum element in max1 int max1 = Int32.MinValue; for ( int i = 0; i < n; i++) { arr[i] = max - arr[i]; if (arr[i] > max1) { max1 = arr[i]; } } // Print the output for ( int i = 0; i < n; i++) { Console.Write((max1 - arr[i]) + " " ); } } } // Driver Code public static void Main() { int N = 6, K = 3; int []arr = { 5, 38, 4, 96, 103, 41 }; // Function call find(N, K, arr); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the approach const INT_MIN = -2147483648; // Function for converting the array const find = (n, k, arr) => { // Find the maximum element in array let max = INT_MIN; for (let i = 0; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // If k is odd if (k % 2 != 0) { for (let i = 0; i < n; i++) { document.write(`${max - arr[i]} `); } } // If k is even else { // Subtract the max from every // element of array and store // the next maximum element in max1 let max1 = INT_MIN; for (let i = 0; i < n; i++) { arr[i] = max - arr[i]; if (arr[i] > max1) { max1 = arr[i]; } } // Print the output for (let i = 0; i < n; i++) { document.write(`${max1 - arr[i]} `); } } } // Driver code let N = 6, K = 3; let arr = [5, 38, 4, 96, 103, 41]; // Function call find(N, K, arr); // This code is contributed by rakeshsahni </script> |
98 65 99 7 0 62
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us