Given an array arr[] of n integers and an integer K. In one operation every element of the array is replaced by the difference of that element and the maximum value of the array. The task is to print the array after performing K operations.
Examples:
Input: arr[] = {4, 8, 12, 16}, k = 2
Output: 0 4 8 12
k = 1, arr[] = {12, 8, 4, 0}
k = 2, arr[] = {0, 4, 8, 12}
Input: arr[] = {14, 28, 14, 106, 223}, k = 12
Output: 0 14 0 92 209
Approach: There are two possible cases:
- If k is odd then the new array will be max(arr) – arr[i] for all i in range [0, n).
- If k is even then the new array will be arr[i] – min(arr) for all i in range [0, n).
For example:
Let arr[] = {4, 8, 12, 16}
For k = 1, arr[] = (12, 8, 4, 0}
For k = 2, arr[] = (0, 4, 8, 12}
For k = 3, arr[] = (12, 8, 4, 0}
For k = 4, arr[] = (0, 4, 8, 12}
It can be observed that the array is repeating after every 2 operations.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Utility function to print// the contents of an arrayvoid printArray(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Function to remove the minimum value of// the array from every element of the arrayvoid removeMin(int arr[], int n){ int i, minVal = arr[0]; // Get the minimum value from the array for (i = 1; i < n; i++) minVal = min(minVal, arr[i]); // Remove the minimum value from // every element of the array for (i = 0; i < n; i++) arr[i] = arr[i] - minVal;}// Function to remove every element of the// array from the maximum value of the arrayvoid removeFromMax(int arr[], int n){ int i, maxVal = arr[0]; // Get the maximum value from the array for (i = 1; i < n; i++) maxVal = max(maxVal, arr[i]); // Remove every element of the array from // the maximum value of the array for (i = 0; i < n; i++) arr[i] = maxVal - arr[i];}// Function to print the modified array// after k operationsvoid modifyArray(int arr[], int n, int k){ // If k is odd then remove the minimum element // of the array from every element of the array if (k % 2 == 0) removeMin(arr, n); // Else remove every element of the array from // the maximum value from the array else removeFromMax(arr, n); // Print the modified array printArray(arr, n);}// Driver codeint main(){ int arr[] = { 4, 8, 12, 16 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; modifyArray(arr, n, k); return 0;} |
Java
// Java implementation of the approachclass GFG { // Utility function to print // the contents of an array static void printArray(int arr[], int n) { for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } // Function to remove the minimum value of // the array from every element of the array static void removeMin(int arr[], int n) { int i, minVal = arr[0]; // Get the minimum value from the array for (i = 1; i < n; i++) minVal = Math.min(minVal, arr[i]); // Remove the minimum value from // every element of the array for (i = 0; i < n; i++) arr[i] = arr[i] - minVal; } // Function to remove every element of the // array from the maximum value of the array static void removeFromMax(int arr[], int n) { int i, maxVal = arr[0]; // Get the maximum value from the array for (i = 1; i < n; i++) maxVal = Math.max(maxVal, arr[i]); // Remove every element of the array from // the maximum value of the array for (i = 0; i < n; i++) arr[i] = maxVal - arr[i]; } // Function to print the modified array // after k operations static void modifyArray(int arr[], int n, int k) { // If k is odd then remove the minimum element // of the array from every element of the array if (k % 2 == 0) removeMin(arr, n); // Else remove every element of the array from // the maximum value from the array else removeFromMax(arr, n); // Print the modified array printArray(arr, n); } // Driver code public static void main(String args[]) { int arr[] = { 4, 8, 12, 16 }; int n = arr.length; int k = 2; modifyArray(arr, n, k); }} |
Python3
# Python 3 implementation of the approach # Utility function to print # the contents of an array def printArray(arr, n) : for i in range(n) : print(arr[i], end = " "); # Function to remove the minimum # value of the array from every # element of the array def removeMin(arr, n) : minVal = arr[0]; # Get the minimum value from # the array for i in range(1, n) : minVal = min(minVal, arr[i]); # Remove the minimum value from # every element of the array for i in range(n) : arr[i] = arr[i] - minVal; # Function to remove every element # of the array from the maximum# value of the array def removeFromMax(arr, n) : maxVal = arr[0]; # Get the maximum value from # the array for i in range(1, n) : maxVal = max(maxVal, arr[i]); # Remove every element of the # array from the maximum value # of the array for i in range(n) : arr[i] = maxVal - arr[i]; # Function to print the modified # array after k operations def modifyArray(arr, n, k) : # If k is odd then remove the minimum # element of the array from every # element of the array if (k % 2 == 0) : removeMin(arr, n); # Else remove every element of # the array from the maximum # value from the array else : removeFromMax(arr, n); # Print the modified array printArray(arr, n); # Driver code if __name__ == "__main__" : arr = [ 4, 8, 12, 16 ]; n = len(arr) k = 2; modifyArray(arr, n, k); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG { // Utility function to print // the contents of an array static void printArray(int[] arr, int n) { for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // Function to remove the minimum value of // the array from every element of the array static void removeMin(int[] arr, int n) { int i, minVal = arr[0]; // Get the minimum value from the array for (i = 1; i < n; i++) minVal = Math.Min(minVal, arr[i]); // Remove the minimum value from // every element of the array for (i = 0; i < n; i++) arr[i] = arr[i] - minVal; } // Function to remove every element of the // array from the maximum value of the array static void removeFromMax(int[] arr, int n) { int i, maxVal = arr[0]; // Get the maximum value from the array for (i = 1; i < n; i++) maxVal = Math.Max(maxVal, arr[i]); // Remove every element of the array from // the maximum value of the array for (i = 0; i < n; i++) arr[i] = maxVal - arr[i]; } // Function to print the modified array // after k operations static void modifyArray(int[] arr, int n, int k) { // If k is odd then remove the minimum element // of the array from every element of the array if (k % 2 == 0) removeMin(arr, n); // Else remove every element of the array from // the maximum value from the array else removeFromMax(arr, n); // Print the modified array printArray(arr, n); } // Driver code public static void Main(String[] args) { int[] arr = { 4, 8, 12, 16 }; int n = arr.Length; int k = 2; modifyArray(arr, n, k); }} |
PHP
<?php// PHP implementation of the approach// Utility function to print// the contents of an arrayfunction printArray($arr, $n){ for ($i = 0; $i < $n; $i++) echo $arr[$i] . " ";}// Function to remove the minimum value of// the array from every element of the arrayfunction removeMin(&$arr, $n){ $minVal = $arr[0]; // Get the minimum value from the array for ($i = 1; $i < $n; $i++) $minVal = min($minVal, $arr[$i]); // Remove the minimum value from // every element of the array for ($i = 0; $i < $n; $i++) $arr[$i] = $arr[$i] - $minVal;}// Function to remove every element of the// array from the maximum value of the arrayfunction removeFromMax(&$arr, $n){ $maxVal = $arr[0]; // Get the maximum value from the array for ($i = 1; $i < $n; $i++) $maxVal = max($maxVal, $arr[$i]); // Remove every element of the array from // the maximum value of the array for ($i = 0; $i < $n; $i++) $arr[$i] = $maxVal - $arr[$i];}// Function to print the modified array// after k operationsfunction modifyArray($arr, $n, $k){ // If k is odd then remove the minimum element // of the array from every element of the array if ($k % 2 == 0) removeMin($arr, $n); // Else remove every element of the array // from the maximum value from the array else removeFromMax($arr, $n); // Print the modified array printArray($arr, $n);}// Driver code$arr = array( 4, 8, 12, 16 );$n = count($arr);$k = 2;modifyArray($arr, $n, $k);// This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of the approach// Utility function to print// the contents of an arrayfunction printArray(arr, n){ for (var i = 0; i < n; i++) document.write(arr[i] + " ");}// Function to remove the minimum value of// the array from every element of the arrayfunction removeMin(arr, n){ var i, minVal = arr[0]; // Get the minimum value from the array for (i = 1; i < n; i++) minVal = Math.min(minVal, arr[i]); // Remove the minimum value from // every element of the array for (i = 0; i < n; i++) arr[i] = arr[i] - minVal;}// Function to remove every element of the// array from the maximum value of the arrayfunction removeFromMax(arr, n){ var i, maxVal = arr[0]; // Get the maximum value from the array for (i = 1; i < n; i++) maxVal = Math.max(maxVal, arr[i]); // Remove every element of the array from // the maximum value of the array for (i = 0; i < n; i++) arr[i] = maxVal - arr[i];}// Function to print the modified array// after k operationsfunction modifyArray(arr, n, k){ // If k is odd then remove the minimum element // of the array from every element of the array if (k % 2 == 0) removeMin(arr, n); // Else remove every element of the array from // the maximum value from the array else removeFromMax(arr, n); // Print the modified array printArray(arr, n);}// Driver codearr = [ 4, 8, 12, 16 ]var n = arr.length;var k = 2;modifyArray(arr, n, k);// This code is contributed by noob2000.</script> |
Output:
0 4 8 12
Time Complexity: O(n), where n represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
