Make all the elements of equal by using given operation
Given an array A[] of length N, the task is to return the minimum number of times the below-given operations are required to perform so that all elements become equal. If it is not possible then return -1.
- Choose two distinct indices i and j. Such that A[i] > A[j]
- Let X = Ceil((A[i] – A[j])/2)
- Subtract X from A[i]
- Add X into A[j]
Examples:
Input: N = 7, A[] = {3, 1, 2, 7, 5, 6, 4}
Output: 3
Explanation:
- First Operation: Take A[0] = 3 and A[4] = 5. Then X = Ceil((5 – 3)/2) = 1. Now, Subtract 1 from A[4] and add 1 into A[0]. Then A[] = {4, 1, 2, 7, 4, 6, 4}
- Second Operation: Take A[5] = 6 and A[2] = 2. Then X = Ceil((6 – 2)/2) = 2. Now, Subtract 2 from A[5] and add 1 into A[2]. Then A[] = {4, 1, 4, 7, 4, 4, 4}
- First Operation: Take A[3] = 7 and A[1] = 1. Then X = Ceil((7 – 1)/2) = 3. Now, Subtract 3 from A[3] and add 1 into A[1]. Then A[] = {4, 4, 4, 4, 4, 4, 4}
Now, It can be verified that all the elements are equal, and the minimum number of operations required is 3.
Input: N = 2, A[] = {1, 2}
Output: -1
Explanation: It can be verified that, it is impossible to make both elements equal using given operation.
Approach: Implement the idea below to solve the problem
The problem is observation based and can be solved using some Mathematics. For finding the minimum number of operations, A[] needed to be sort.
Steps were taken to solve the problem:
- Declare an integer variable sum to store the sum of elements in the array.
- Create a multiset of integers named mset to maintain a sorted set of elements.
- Iterate through the elements of vector A, calculate the sum of elements, and insert each element into the multiset.
- Check if the sum of elements (sum) is not divisible by the total number of elements (N). If so, return -1, as making the elements equal is not possible.
- Declare an integer variable min and initialize it to 0 to store the minimum number of operations required.
- Enter a loop that continues until the multiset is not empty:
- Find the minimum element in the multiset and store it in minElement.
- Find the maximum element in the multiset and store it in maxElement.
- If minElement is equal to maxElement, exit the loop as all elements are equal.
- Calculate the difference between maxElement and minElement and update it as (diff / 2) + (diff % 2).
- Erase both minElement and maxElement from the multiset.
- Add diff to minElement and subtract it from maxElement.
- Insert the updated minElement and maxElement back into the multiset.
- Increment the min variable by 1.
- Return the value stored in the min variable, representing t
Code to implement the approach:
C++14
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int min_operations( int N, vector< int >& A) { // Variable to store the sum of A[] int sum = 0; // Multiset to maintain a sorted // set of elements multiset< int > mset; // Loop for iterating A[] and /// initializing sum and multiset for ( int i = 0; i < N; i++) { sum += A[i]; mset.insert(A[i]); } // Condition when making elements // equal is not possible if (sum % N != 0) { return -1; } // Variable to store minimum operations int min = 0; // Making max and minimum element // equal in each operation while (!mset.empty()) { int minElement = *mset.begin(); int maxElement = *prev(mset.end()); if (minElement == maxElement) { break ; } int diff = maxElement - minElement; diff = (diff / 2) + (diff % 2); // Remove and update the multiset mset.erase(mset.begin()); mset.erase(prev(mset.end())); minElement += diff; maxElement -= diff; mset.insert(minElement); mset.insert(maxElement); min++; } return min; } // Drivers code int main() { int N = 7; vector< int > A = { 1, 2, 3, 4, 5, 6, 7 }; // Function Call int result = min_operations(N, A); cout << result << endl; return 0; } |
Java
/*package whatever //do not write package name here */ //code contributed by Flutterfly import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Main { public static int minOperations( int N, List<Integer> A) { // Variable to store the sum of A[] int sum = 0 ; // List to maintain a sorted // set of elements List<Integer> list = new ArrayList<>(A); // Loop for iterating A[] and // initializing sum for ( int i = 0 ; i < N; i++) { sum += list.get(i); } // Condition when making elements // equal is not possible if (sum % N != 0 ) { return - 1 ; } // Variable to store minimum operations int min = 0 ; // Making max and minimum element // equal in each operation while (!list.isEmpty()) { int minElement = Collections.min(list); int maxElement = Collections.max(list); if (minElement == maxElement) { break ; } int diff = maxElement - minElement; diff = (diff / 2 ) + (diff % 2 ); // Remove and update the list list.remove(Integer.valueOf(minElement)); list.remove(Integer.valueOf(maxElement)); minElement += diff; maxElement -= diff; list.add(minElement); list.add(maxElement); min++; } return min; } //Driver's Code public static void main(String[] args) { int N = 7 ; List<Integer> A = new ArrayList<>(); A.add( 1 ); A.add( 2 ); A.add( 3 ); A.add( 4 ); A.add( 5 ); A.add( 6 ); A.add( 7 ); // Function Call int result = minOperations(N, A); System.out.println(result); } } |
Python
# code contributed by Flutterfly def min_operations(N, A): # Variable to store the sum of A[] sum = 0 # Set to maintain a sorted set of elements mset = set () # Loop for iterating A[] and initializing sum and set for i in range (N): sum + = A[i] mset.add(A[i]) # Condition when making elements equal is not possible if sum % N ! = 0 : return - 1 # Variable to store minimum operations min_ops = 0 # Making max and minimum element equal in each operation while mset: min_element = min (mset) max_element = max (mset) if min_element = = max_element: break diff = max_element - min_element diff = (diff / / 2 ) + (diff % 2 ) # Remove and update the set mset.remove(min_element) mset.remove(max_element) min_element + = diff max_element - = diff mset.add(min_element) mset.add(max_element) min_ops + = 1 return min_ops # Driver code N = 7 A = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] # Function Call result = min_operations(N, A) print (result) |
C#
using System; using System.Collections.Generic; class Program { static int MinOperations( int N, List< int > A) { // Variable to store the sum of A[] int sum = 0; // SortedSet to maintain a sorted // set of elements SortedSet< int > sortedSet = new SortedSet< int >(); // Loop for iterating A[] and // initializing sum and Sortedset for ( int i = 0; i < N; i++) { sum += A[i]; sortedSet.Add(A[i]); } // Condition when making elements // equal is not possible if (sum % N != 0) { return -1; } // Variable to store minimum operations int min = 0; // Making max and minimum element // equal in each operation while (sortedSet.Count > 0) { int minElement = sortedSet.Min; int maxElement = sortedSet.Max; if (minElement == maxElement) { break ; } int diff = maxElement - minElement; diff = (diff / 2) + (diff % 2); // Remove and update the Sortedset sortedSet.Remove(minElement); sortedSet.Remove(maxElement); minElement += diff; maxElement -= diff; sortedSet.Add(minElement); sortedSet.Add(maxElement); min++; } return min; } //Driver's Code static void Main( string [] args) { int N = 7; List< int > A = new List< int > { 1, 2, 3, 4, 5, 6, 7 }; // Function Call int result = MinOperations(N, A); Console.WriteLine(result); } } |
Javascript
function min_operations(N, A) { // Variable to store the sum of A[] let sum = 0; // Multiset to maintain a sorted // set of elements let mset = new Set(); // Loop for iterating A[] and // initializing sum and multiset for (let i = 0; i < N; i++) { sum += A[i]; mset.add(A[i]); } // Condition when making elements // equal is not possible if (sum % N !== 0) { return -1; } // Variable to store minimum operations let min = 0; // Making max and minimum element // equal in each operation while (mset.size > 0) { let minElement = Math.min(...mset); let maxElement = Math.max(...mset); if (minElement === maxElement) { break ; } let diff = maxElement - minElement; diff = Math.floor(diff / 2) + (diff % 2); // Remove and update the multiset mset. delete (minElement); mset. delete (maxElement); mset.add(minElement + diff); mset.add(maxElement - diff); min++; } return min; } //Driver's Code let N = 7; let A = [1, 2, 3, 4, 5, 6, 7]; // Function Call let result = min_operations(N, A); console.log(result); |
3
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Contact Us