Minimum operations to make Array equal by repeatedly adding K from an element and subtracting K from other
Given an array arr[] and an integer K, the task is to find the minimum number of operations to make all the elements of the array arr[] equal. In one operation, K is subtracted from an element and this K is added into other element. If it is not possible then print -1.
Examples:
Input: arr[] = {5, 8, 11}, K = 3
Output: 1
Explanation:
Operation 1: Subtract 3 from arr[2](=11) and add 3 to arr[0](=5).
Now, all the elements of the array arr[] are equal.Input: arr[] = {1, 2, 3, 4}, K = 2
Output: -1
Approach: This problem can be solved using the Greedy algorithm. First check the sum of all elements of the array arr[] is divisible by N or not. If it is not divisible that means it is impossible to make all elements of the array arr[] equal. Otherwise, try to add or subtract the value of K to make every element equal to sum of arr[] / N. Follow the steps below to solve this problem:
- Initialize a variable sum as 0 to store sum of all elements of the array arr[].
- Iterate in the range [0, N-1] using the variable i and update sum as sum + arr[i].
- If sum % N is not equal to 0, then print -1 and return.
- Initialize a variable valueAfterDivision as sum/N to store that this much value, each element of array arr[] is store and count as 0 to store the minimum number of operation needed to make all array element equal.
- Iterate in the range [0, N-1] using the variable i:
- After completing the above steps, print count/2 as the answer.
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 the minimum number of // operations to make all the elements of // the array equal void miniOperToMakeAllEleEqual( int arr[], int n, int k) { // Store the sum of the array arr[] int sum = 0; // Traverse through the array for ( int i = 0; i < n; i++) { sum += arr[i]; } // If it is not possible to make all // array element equal if (sum % n) { cout << -1; return ; } int valueAfterDivision = sum / n; // Store the minimum number of operations needed int count = 0; // Traverse through the array for ( int i = 0; i < n; i++) { if ( abs (valueAfterDivision - arr[i]) % k != 0) { cout << -1; return ; } count += abs (valueAfterDivision - arr[i]) / k; } // Finally, print the minimum number operation // to make array elements equal cout << count / 2 << endl; } // Driver Code int main() { // Given Input int n = 3, k = 3; int arr[3] = { 5, 8, 11 }; // Function Call miniOperToMakeAllEleEqual(arr, n, k); // This code is contributed by Potta Lokesh return 0; } |
Java
// Java Program for the above approach import java.io.*; class GFG { // Function to find the minimum number of // operations to make all the elements of // the array equal static void miniOperToMakeAllEleEqual( int arr[], int n, int k) { // Store the sum of the array arr[] int sum = 0 ; // Traverse through the array for ( int i = 0 ; i < n; i++) { sum += arr[i]; } // If it is not possible to make all // array element equal if (sum % n != 0 ) { System.out.println(- 1 ); return ; } int valueAfterDivision = sum / n; // Store the minimum number of operations needed int count = 0 ; // Traverse through the array for ( int i = 0 ; i < n; i++) { if (Math.abs(valueAfterDivision - arr[i]) % k != 0 ) { System.out.println(- 1 ); return ; } count += Math.abs(valueAfterDivision - arr[i]) / k; } // Finally, print the minimum number operation // to make array elements equal System.out.println(( int )count / 2 ); } // Driver Code public static void main (String[] args) { // Given Input int n = 3 , k = 3 ; int arr[] = { 5 , 8 , 11 }; // Function Call miniOperToMakeAllEleEqual(arr, n, k); } } // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach # Function to find the minimum number of # operations to make all the elements of # the array equal def miniOperToMakeAllEleEqual(arr, n, k): # Store the sum of the array arr[] sum = 0 # Traverse through the array for i in range (n): sum + = arr[i] # If it is not possible to make all # array element equal if ( sum % n): print ( - 1 ) return valueAfterDivision = sum / / n # Store the minimum number of operations needed count = 0 # Traverse through the array for i in range (n): if ( abs (valueAfterDivision - arr[i]) % k ! = 0 ): print ( - 1 ) return count + = abs (valueAfterDivision - arr[i]) / / k # Finally, print the minimum number operation # to make array elements equal print (count / / 2 ) # Driver Code if __name__ = = '__main__' : # Given Input n = 3 k = 3 arr = [ 5 , 8 , 11 ] # Function Call miniOperToMakeAllEleEqual(arr, n, k) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; class GFG { // Function to find the minimum number of // operations to make all the elements of // the array equal static void miniOperToMakeAllEleEqual( int [] arr, int n, int k) { // Store the sum of the array arr[] int sum = 0; // Traverse through the array for ( int i = 0; i < n; i++) { sum += arr[i]; } // If it is not possible to make all // array element equal if (sum % n != 0) { Console.WriteLine(-1); return ; } int valueAfterDivision = sum / n; // Store the minimum number of operations needed int count = 0; // Traverse through the array for ( int i = 0; i < n; i++) { if (Math.Abs(valueAfterDivision - arr[i]) % k != 0) { Console.WriteLine(-1); return ; } count += Math.Abs(valueAfterDivision - arr[i]) / k; } // Finally, print the minimum number operation // to make array elements equal Console.WriteLine(( int )count / 2); } static void Main() { // Given Input int n = 3, k = 3; int [] arr = { 5, 8, 11 }; // Function Call miniOperToMakeAllEleEqual(arr, n, k); } } // This code is contributed by abhinavjain194 |
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum number of // operations to make all the elements of // the array equal function miniOperToMakeAllEleEqual(arr, n, k) { // Store the sum of the array arr[] let sum = 0; // Traverse through the array for (let i = 0; i < n; i++) { sum += arr[i]; } // If it is not possible to make all // array element equal if (sum % n) { document.write(-1); return ; } let valueAfterDivision = sum / n; // Store the minimum number of operations needed let count = 0; // Traverse through the array for (let i = 0; i < n; i++) { if (Math.abs(valueAfterDivision - arr[i]) % k != 0) { document.write(-1); return ; } count += Math.abs(valueAfterDivision - arr[i]) / k; } // Finally, print the minimum number operation // to make array elements equal document.write(Math.floor(count / 2)); } // Driver Code // Given Input let n = 3, k = 3; let arr = [5, 8, 11]; // Function Call miniOperToMakeAllEleEqual(arr, n, k); // This code is contributed by Potta Lokesh </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)