Minimize subtraction followed by increments of adjacent elements required to make all array elements equal
Given an array arr[] consisting of N positive integers, the task is to make all array elements equal by repeatedly subtracting 1 from any number of array elements and add it to one of the adjacent elements at the same time. If all array elements can’t be made equal, then print “-1”. Otherwise, print the minimum count of operations required.
Examples:
Input: arr[] = {1, 0, 5}
Output: 3
Explanation:
Operation 1: Subtract arr[2](= 5) by 1 and add it to arr[1](= 0). Therefore, the array arr[] modifies to {1, 1, 4}.
Operation 2: Subtract arr[2](= 4) by 1 and add it to arr[1](= 1). Therefore, the array arr[] modifies to {1, 2, 3}.
Operation 3: Subtract arr[2](= 3) and arr[1](= 2) by 1 and add it to arr[1](= 1) and arr[2](= 2) respectively. Therefore, the array arr[] modifies to {2, 2, 2}.Therefore, the minimum number of operations required is 3.
Input: arr[] = {0, 3, 0}
Output: 2
Approach: The given problem can be solved based on the following observation:
- All the array elements can be made equal if and only if the value of all array elements is equal to the average of the array.
- Since only 1 can be subtracted from an array element at a time, the minimum number of moves is the maximum of the prefix sum of the array or the number of moves required to make each element equal to the average of the array.
Follow the steps below to solve the problem:
- Calculate the sum of the elements of the array arr[], say S.
- If the sum S is not divisible by N, then print “-1”.
- Otherwise, perform the following operations:
- Store the average of array elements in a variable, say avg.
- Initialize two variables, say total and count with 0, to store the required result and the prefix sum of minimum moves to achieve avg respectively.
- Traverse the given array arr[] and perform the following steps:
- Add the value of (arr[i] – avg) to the count.
- Update the value of total to the maximum of the absolute value of count, total, (arr[i] – avg).
- After completing the above step, print the value of total as the resultant minimum operation required.
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 moves required to make all array // elements equal int findMinMoves( int arr[], int N) { // Store the total sum of the array int sum = 0; // Calculate total sum of the array for ( int i = 0; i < N; i++) sum += arr[i]; // If the sum is not divisible // by N, then print "-1" if (sum % N != 0) return -1; // Stores the average int avg = sum / N; // Stores the count // of operations int total = 0; int needCount = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update number of moves // required to make current // element equal to avg needCount += (arr[i] - avg); // Update the overall count total = max({ abs (needCount),arr[i] - avg,total}); } // Return the minimum // operations required return total; } // Driver Code int main() { int arr[] = { 1, 0, 5 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findMinMoves(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to find the minimum number // of moves required to make all array // elements equal static int findMinMoves( int [] arr, int N) { // Store the total sum of the array int sum = 0 ; // Calculate total sum of the array for ( int i = 0 ; i < N; i++) sum += arr[i]; // If the sum is not divisible // by N, then print "-1" if (sum % N != 0 ) return - 1 ; // Stores the average int avg = sum / N; // Stores the count // of operations int total = 0 ; int needCount = 0 ; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Update number of moves // required to make current // element equal to avg needCount += (arr[i] - avg); // Update the overall count total = Math.max( Math.max(Math.abs(needCount), arr[i] - avg), total); } // Return the minimum // operations required return total; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 0 , 5 }; int N = arr.length; System.out.println(findMinMoves(arr, N)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to find the minimum number # of moves required to make all array # elements equal def findMinMoves(arr, N): # Store the total sum of the array sum = 0 # Calculate total sum of the array for i in range (N): sum + = arr[i] # If the sum is not divisible # by N, then print "-1" if ( sum % N ! = 0 ): return - 1 # Stores the average avg = sum / / N # Stores the count # of operations total = 0 needCount = 0 # Traverse the array arr[] for i in range (N): # Update number of moves # required to make current # element equal to avg needCount + = (arr[i] - avg) # Update the overall count total = max ( max ( abs (needCount), arr[i] - avg), total) # Return the minimum # operations required return total # Driver Code if __name__ = = '__main__' : arr = [ 1 , 0 , 5 ] N = len (arr) print (findMinMoves(arr, N)) # This code is contributed by bgangwar59. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum number // of moves required to make all array // elements equal static int findMinMoves( int [] arr, int N) { // Store the total sum of the array int sum = 0; // Calculate total sum of the array for ( int i = 0; i < N; i++) sum += arr[i]; // If the sum is not divisible // by N, then print "-1" if (sum % N != 0) return -1; // Stores the average int avg = sum / N; // Stores the count // of operations int total = 0; int needCount = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update number of moves // required to make current // element equal to avg needCount += (arr[i] - avg); // Update the overall count total = Math.Max( Math.Max(Math.Abs(needCount), arr[i] - avg), total); } // Return the minimum // operations required return total; } // Driver Code public static void Main() { int [] arr = { 1, 0, 5 }; int N = arr.Length; Console.Write(findMinMoves(arr, N)); } } // This code is contributed by ukasp |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum number // of moves required to make all array // elements equal function findMinMoves(arr, N) { // Store the total sum of the array let sum = 0; // Calculate total sum of the array for (let i = 0; i < N; i++) sum += arr[i]; // If the sum is not divisible // by N, then print "-1" if (sum % N != 0) return -1; // Stores the average let avg = sum / N; // Stores the count // of operations let total = 0; let needCount = 0; // Traverse the array arr[] for (let i = 0; i < N; i++) { // Update number of moves // required to make current // element equal to avg needCount += (arr[i] - avg); // Update the overall count total = Math.max(Math.max( Math.abs(needCount), arr[i] - avg), total); } // Return the minimum // operations required return total; } // Driver Code let arr = [ 1, 0, 5 ]; let N = arr.length; document.write(findMinMoves(arr, N)) // This code is contributed by Hritik </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)