Minimizing Moves to Equalize Array Elements using Greedy Approach
- Check if the total sum can be evenly distributed among the elements or not.
- Once you have the target value, iterate through the array from left to right. At each element, maintain a running balance, which represents the difference between the actual value of the element and the target value.
- To determine the moves needed, consider two cases:
- a) If the running balance is positive (i.e., there are excess items in the current element), we need to pass these items to the adjacent elements. For example, if we have a running balance of 5 and the current element has 2 excess items, we would need to pass a total of (5 + 2) = 7 items through that element (which requires 7 moves).
- b) We also keep track of the number of items that need to be offloaded from the current element to reach the target value (arr[i] – target). This number might be higher than the running balance if items need to be passed both ways (to and from the current element).
- The minimum number of moves needed for the entire array can be find by taking the maximum of the following two values at each step:
- The difference between the current element and the target value (arr[i] – target).
- The absolute value of the running balance (abs(running balance)).
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the minimum moves // to equalize the array elements int findMinMoves(vector< int >& arr) { int totalElements = 0, size = arr.size(); // Calculate the total number of // elements in the array for ( auto i = 0; i < size; ++i) totalElements += arr[i]; // If the total number of elements // cannot be evenly distributed, // return -1 if (totalElements % size != 0) return -1; // Calculate the target number // of element at each place auto target = totalElements / size, totalMoves = 0, balance = 0; // Iterate through each array // element to calculate the moves // needed to balance elements for ( auto i = 0; i < size; ++i) { // Calculate the balance of // dresses in the current element balance += arr[i] - target; // Update the total moves // needed as the maximum of // the current balance // and previous moves totalMoves = max( totalMoves, max(arr[i] - target, abs (balance))); } // Return the minimum moves // required to equalize the elements return totalMoves; } // Driver code int main() { vector< int > arr = { 1, 0, 5 }; // Function Call cout << findMinMoves(arr); return 0; } |
Java
import java.util.*; public class Main { // Function to find the minimum moves to equalize the array elements public static int findMinMoves(List<Integer> arr) { int totalElements = 0 ; int size = arr.size(); // Calculate the total number of elements in the array for ( int i = 0 ; i < size; i++) { totalElements += arr.get(i); } // If the total number of elements cannot be evenly distributed, return -1 if (totalElements % size != 0 ) { return - 1 ; } // Calculate the target number of elements at each place int target = totalElements / size; int totalMoves = 0 ; int balance = 0 ; // Iterate through each array element to calculate the moves needed to balance elements for ( int i = 0 ; i < size; i++) { // Calculate the balance of dresses in the current element balance += arr.get(i) - target; // Update the total moves needed as the maximum of the current balance and previous moves totalMoves = Math.max(totalMoves, Math.max(arr.get(i) - target, Math.abs(balance))); } // Return the minimum moves required to equalize the elements return totalMoves; } public static void main(String[] args) { List<Integer> arr = Arrays.asList( 1 , 0 , 5 ); // Function Call System.out.println(findMinMoves(arr)); } } |
Python3
def find_min_moves(arr): total_elements = sum (arr) size = len (arr) # Calculate the total number of elements in the array if total_elements % size ! = 0 : return - 1 # Calculate the target number of elements at each place target = total_elements / / size total_moves = 0 balance = 0 # Iterate through each array element to calculate the moves needed to balance elements for i in range (size): # Calculate the balance of dresses in the current element balance + = arr[i] - target # Update the total moves needed as the maximum of the current balance and previous moves total_moves = max (total_moves, max (arr[i] - target, abs (balance))) # Return the minimum moves required to equalize the elements return total_moves # Driver code if __name__ = = "__main__" : arr = [ 1 , 0 , 5 ] # Function Call print (find_min_moves(arr)) |
C#
using System; using System.Collections.Generic; class Program { // Function to find the minimum moves // to equalize the array elements static int FindMinMoves(List< int > arr) { int totalElements = 0; int size = arr.Count; // Calculate the total number of // elements in the array for ( int i = 0; i < size; ++i) { totalElements += arr[i]; } // If the total number of elements // cannot be evenly distributed, // return -1 if (totalElements % size != 0) { return -1; } // Calculate the target number // of element at each place int target = totalElements / size; int totalMoves = 0; int balance = 0; // Iterate through each array // element to calculate the moves // needed to balance elements for ( int i = 0; i < size; ++i) { // Calculate the balance of // dresses in the current element balance += arr[i] - target; // Update the total moves // needed as the maximum of // the current balance // and previous moves totalMoves = Math.Max(totalMoves, Math.Max(arr[i] - target, Math.Abs(balance))); } // Return the minimum moves // required to equalize the elements return totalMoves; } // Driver code static void Main() { List< int > arr = new List< int > { 1, 0, 5 }; // Function Call Console.WriteLine(FindMinMoves(arr)); } } // This code is contributed by shivamgupta0987654321 |
Javascript
function findMinMoves(arr) { let totalElements = 0; const size = arr.length; // Calculate the total number of elements in the array for (let i = 0; i < size; ++i) { totalElements += arr[i]; } // If the total number of elements cannot be evenly distributed, return -1 if (totalElements % size !== 0) { return -1; } // Calculate the target number of element at each place const target = totalElements / size; let totalMoves = 0; let balance = 0; // Iterate through each array element to calculate the moves needed to balance elements for (let i = 0; i < size; ++i) { // Calculate the balance of dresses in the current element balance += arr[i] - target; // Update the total moves needed as the maximum of the current balance and previous moves totalMoves = Math.max(totalMoves, Math.max(arr[i] - target, Math.abs(balance))); } // Return the minimum moves required to equalize the elements return totalMoves; } // Driver code const arr = [1, 0, 5]; // Function Call console.log(findMinMoves(arr)); |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Minimizing Moves to Equalize Array Elements
Given an array arr[] of N integers, For each move, you can select any m (1 <= m <= n) elements from the array and transfer one integer unit from each selected element to one of its adjacent elements at the same time, the task is to find the minimum number of moves needed to make all the integers in the array equal. If it’s not possible to achieve this, return -1.
Examples:
Input: arr = {1, 0, 5}
Output: 3
Explanation: 1st move: 1 0 <– 5 => 1 1 4
2nd move: 1 <– 1 <– 4 => 2 1 3
3rd move: 2 1 <– 3 => 2 2 2Input: arr = [0,3,0]
Output: 2
Explanation: 1st move: 0 <– 3 0 => 1 2 0
2nd move: 1 2 –> 0 => 1 1 1