Minimize absolute difference between the smallest and largest array elements by minimum increment decrement operations
Given an array arr[] consisting of N positive integers, the task is to minimize the number of operations required to minimize the absolute difference between the smallest and largest elements present in the array. In each operation, subtract 1 from an array element and increment 1 to another array element.
Examples:
Input: arr[] = {1, 6}
Output: 2
Explanation:
Below are the operations performed:
Operation 1: Subtracting 1 from 2nd element and adding 1 to 1st element modifies the array to {2, 5}.
Operation2: Subtracting 1 from 2nd element and adding 1 to 1st element modifies the array to {3, 4}.
After the above operations, the absolute difference between the minimum and the maximum element is (4 – 3) = 1, which is minimum and number of operation required is 2.Input: arr[] = {1, 2, 2, 1, 1}
Output: 0
Approach: The given problem can be solved by observing the fact that increment and decrement of an array element by 1 are performed in pairs so if the sum of the array element is divisible by N then all array elements can be made sum/N. Otherwise, some elements will have the value sum/N, and some elements will have value (sum/N + 1) after performing the given operations. Follow the steps below to solve the given problem:
- Initialize an auxiliary array, say final[] that stores the resultant array having the required minimum difference.
- Sort the given array in increasing order.
- Traverse the given array and if the current index i is less than sum%N, then update the current element of the final array to the value (sum/N + 1). Otherwise, update final[i] to (sum/N).
- Reverse the array final[].
- Initialize a variable, say ans = 0 that stores the minimum number of operations to convert arr[] to final[].
- Traverse both the arrays arr[] and final[] simultaneously and add the absolute value of the difference of arr[i] and final[i] to the variable ans.
- After completing the above steps, print the value of ans/2 as the resultant minimum operation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs void countMinimumSteps( int arr[], int N) { // Stores the sum of the array int sum = 0; // Find the sum of array element for ( int i = 0; i < N; i++) { sum += arr[i]; } // Stores the resultant final array int finalArray[N]; // Iterate over the range [0, N] for ( int i = 0; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = sum / N + 1; } else { finalArray[i] = sum / N; } } // Reverse the final array reverse(finalArray, finalArray + N); // Stores the minimum number of // operations required int ans = 0; // Update the value of ans for ( int i = 0; i < N; ++i) { ans += abs (arr[i] - finalArray[i]); } // Print the result cout << ans / 2; } // Driver Code int main() { int arr[] = { 1, 6 }; int N = sizeof (arr) / sizeof (arr[0]); countMinimumSteps(arr, N); return 0; } |
Java
// Java program for the above approach class GFG{ static void reverse( int a[], int n) { int i, k, t; for (i = 0 ; i < n / 2 ; i++) { t = a[i]; a[i] = a[n - i - 1 ]; a[n - i - 1 ] = t; } } // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs static void countMinimumSteps( int arr[], int N) { // Stores the sum of the array int sum = 0 ; // Find the sum of array element for ( int i = 0 ; i < N; i++) { sum += arr[i]; } // Stores the resultant final array int finalArray[] = new int [N]; // Iterate over the range [0, N] for ( int i = 0 ; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = sum / N + 1 ; } else { finalArray[i] = sum / N; } } // Reverse the final array reverse(finalArray, finalArray.length); // Stores the minimum number of // operations required int ans = 0 ; // Update the value of ans for ( int i = 0 ; i < N; ++i) { ans += Math.abs(arr[i] - finalArray[i]); } // Print the result System.out.println(ans / 2 ); } // Driver code public static void main(String[] args) { int arr[] = { 1 , 6 }; int N = arr.length; countMinimumSteps(arr, N); } } // This code is contributed by abhinavjain194 |
Python3
# Python program for the above approach # Function to minimize the operations # for the difference between minimum # and maximum element by incrementing # decrementing array elements in pairs def countMinimumSteps(arr, N): # Stores the sum of the array sum = 0 ; # Find the sum of array element for i in range (N): sum + = arr[i]; # Stores the resultant final array finalArray = [ 0 ] * N; # Iterate over the range [0, N] for i in range ( 0 , N): #print(i) # Assign values to finalArray if (i < sum % N): finalArray[i] = ( sum / / N) + 1 ; else : finalArray[i] = sum / / N; # Reverse the final array finalArray = finalArray[:: - 1 ]; # Stores the minimum number of # operations required ans = 0 ; # Update the value of ans for i in range (N): ans + = abs (arr[i] - finalArray[i]); # Print the result print (ans / / 2 ); # Driver Code arr = [ 1 , 6 ]; N = len (arr); countMinimumSteps(arr, N); # This code is contributed by _saurabh_jaiswal. |
C#
// C# program for the above approach using System; class GFG{ static void reverse( int [] a, int n) { int i, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs static void countMinimumSteps( int [] arr, int N) { // Stores the sum of the array int sum = 0; // Find the sum of array element for ( int i = 0; i < N; i++) { sum += arr[i]; } // Stores the resultant final array int [] finalArray = new int [N]; // Iterate over the range [0, N] for ( int i = 0; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = sum / N + 1; } else { finalArray[i] = sum / N; } } // Reverse the final array reverse(finalArray, finalArray.Length); // Stores the minimum number of // operations required int ans = 0; // Update the value of ans for ( int i = 0; i < N; ++i) { ans += Math.Abs(arr[i] - finalArray[i]); } // Print the result Console.WriteLine(ans / 2); } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 6 }; int N = arr.Length; countMinimumSteps(arr, N); } } // This code is contributed by target_2 |
Javascript
<script> // Javascript program for the above approach // Function to minimize the operations // for the difference between minimum // and maximum element by incrementing // decrementing array elements in pairs function countMinimumSteps(arr, N) { // Stores the sum of the array let sum = 0; // Find the sum of array element for (let i = 0; i < N; i++) { sum += arr[i]; } // Stores the resultant final array let finalArray = new Array(N); // Iterate over the range [0, N] for (let i = 0; i < N; ++i) { // Assign values to finalArray if (i < sum % N) { finalArray[i] = Math.floor(sum / N + 1); } else { finalArray[i] = Math.floor(sum / N); } } // Reverse the final array finalArray.reverse(); // Stores the minimum number of // operations required let ans = 0; // Update the value of ans for (let i = 0; i < N; ++i) { ans += Math.abs(arr[i] - finalArray[i]); } // Print the result document.write(Math.floor(ans / 2)); } // Driver Code let arr = [1, 6]; let N = arr.length countMinimumSteps(arr, N); // This code is contributed by _saurabh_jaiswal. </script> |
2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)