Horje
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);

Output

3

Time Complexity: O(N*logN)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Minimum Breaks to make the Array sorted Minimum Breaks to make the Array sorted
Maximizing product of elements with same Digit Product Maximizing product of elements with same Digit Product
Find the maximum sum path in the given Matrix Find the maximum sum path in the given Matrix
Find the Pair of Nodes with the Smallest Product in a Doubly Linked List Find the Pair of Nodes with the Smallest Product in a Doubly Linked List
Fill the Matrix by following the given conditions Fill the Matrix by following the given conditions

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje