Given an array arr[] of size N and a positive integer K, the task is to maximise difference between the largest element and the smallest element in the array by performing at most K operations, wherein each operation:
- select two integers arr[i] and arr[j] from the array and
- update arr[i] to arr[i] – X and arr[j] to arr[j] + X, where X is any integer in range [0, min(arr[i], arr[j])].
Examples:
Input: arr[] = {3, 3, 2, 3, 3}, K = 1
Output: 6
Explanation: In the 1st operation select the integers (arr[1], arr[0]) and X as 3. Hence arr[1] = arr[1] – X = 3 – 3 = 0. Similarly, arr[0] = arr[0] + X = 3 + 3 = 6. Hence, arr[] = {6, 0, 2, 3, 3} and the diffecence between smallest and largest element is 6 which is the maximum possible.Input: arr[] = {7, 4, 8, 11, 2, 23, 67, 22, 5, 29, 6, 4, 56}, N = 13, X = 5
Output: 208
Approach: The given problem can be solved by using a greedy approach. The idea is to maximize the value of the largest element of the array. It can also be observed that the smallest element that can be achieved in the array is 0. Below are the steps to follow:
- Sort the given array arr[] in descending order.
- Iterate through the array in the range [1, N) and perform the given operation on (arr[i], arr[0]) for X = arr[i].
- After K operations have been performed, arr[0] will be the required answer, except for the case where K =0.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum difference// between the largest and smallest// element of arr[] after K operationsint maxDifference(int arr[], int N, int K){ // Sort A in descending order sort(arr, arr + N, greater<int>()); // Case where no operation // is to be performed if (K == 0) { return arr[0] - arr[N - 1]; } // Loop to iterate arr[] for (int i = 1; i < N && K != 0; ++i) { // Update arr[0] // and arr[i] arr[0] += arr[i]; arr[i] = 0; // Decrement K K--; } // Return Answer return arr[0];}// Driver Codeint main(){ int arr[] = { 3, 3, 2, 3, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 1; cout << maxDifference(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to find maximum difference // between the largest and smallest // element of arr[] after K operations static int maxDifference(Integer[] arr, int N, int K) { // Sort A in descending order Arrays.sort(arr, Collections.reverseOrder()); // Case where no operation // is to be performed if (K == 0) { return arr[0] - arr[N - 1]; } // Loop to iterate arr[] for (int i = 1; i < N && K != 0; ++i) { // Update arr[0] // and arr[i] arr[0] += arr[i]; arr[i] = 0; // Decrement K K--; } // Return Answer return arr[0]; } // Driver Code public static void main (String[] args) { Integer[] arr = { 3, 3, 2, 3, 3 }; int N = arr.length; int K = 1; System.out.print(maxDifference(arr, N, K)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python program for the above approach# Function to find maximum difference# between the largest and smallest# element of arr[] after K operationsdef maxDifference(arr, N, K): # Sort A in descending order arr.sort(reverse = True) # Case where no operation # is to be performed if (K == 0): return arr[0] - arr[N - 1] # Loop to iterate arr[] for i in range(1, N): # Update arr[0] # and arr[i] if(K != 0): arr[0] = arr[0] + arr[i] arr[i] = 0 # Decrement K K = K - 1 # Return Answer return arr[0]# Driver Codearr = [3, 3, 2, 3, 3]N = len(arr)K = 1print(maxDifference(arr, N, K))# This code is contributed by Taranpreet |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find maximum difference // between the largest and smallest // element of arr[] after K operations static int maxDifference(int[] arr, int N, int K) { // Sort A in descending order Array.Sort(arr); Array.Reverse(arr); // Case where no operation // is to be performed if (K == 0) { return arr[0] - arr[N - 1]; } // Loop to iterate arr[] for (int i = 1; i < N && K != 0; ++i) { // Update arr[0] // and arr[i] arr[0] += arr[i]; arr[i] = 0; // Decrement K K--; } // Return Answer return arr[0]; }// Driver Codepublic static void Main(){ int[] arr = { 3, 3, 2, 3, 3 }; int n = arr.Length; int k = 1; Console.Write(maxDifference(arr, n, k)); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Function to find maximum difference // between the largest and smallest // element of arr[] after K operations function maxDifference(arr, N, K) { // Sort A in descending order arr.sort(function (a, b) { return b - a }) // Case where no operation // is to be performed if (K == 0) { return arr[0] - arr[N - 1]; } // Loop to iterate arr[] for (let i = 1; i < N && K != 0; ++i) { // Update arr[0] // and arr[i] arr[0] += arr[i]; arr[i] = 0; // Decrement K K--; } // Return Answer return arr[0]; } // Driver Code let arr = [3, 3, 2, 3, 3]; let N = arr.length; let K = 1; document.write(maxDifference(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
6
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
