Given an array arr[] consisting of N non-negative integers, the task is to find the number of operations required to make all array elements equal. In each operation, any array element can be changed to its nearest smaller array element.
Examples:
Input: arr[] = {2, 5, 4, 3, 5, 4}
Output: 11
Explanation:
Step 1: Replace all 5s with 4s. Therefore, arr[] = {2, 4, 4, 3, 4, 4}. Count of operations = 2
Step 2: Replace all 4s with 3s. Therefore, arr[] = {2, 3, 3, 3, 3, 3}. Count of operations = 4
Steps 3: Replace all 3s with 2s. Therefore, arr[] = {2, 2, 2, 2, 2, 2}. Count of operations = 5
Therefore, total number of operations = 11Input : arr[] = {2, 2, 2}
Output : 0
Approach: The idea is to use a sorting algorithm and a Map data structure. Follow the steps below to solve the problem:
- Initialize a Map to store the frequency of each array element except for the minimum element where keys (K) are the set of unique elements and values (V) are their frequencies.
- Sort the Map in decreasing order based on the keys.
- Initialize two variables ans and prev_val with 0 to store the current answer and the prefix sum respectively.
- Now iterate the Map and add the corresponding frequencies of each element along with prev_val to ans as ans = ans + (freq) + prev_val
- While iterating the Map, increment prev_val every time by the frequency of the current element.
- After traversing the Map completely, print ans as the minimum number of operations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the minimum number of// decrements to make all elements equalsint MinimumNoOfOperations(int arr[], int n){ // Find minimum element int min_ele = INT_MAX; for (int i = 0; i < n; ++i) { min_ele = min(min_ele, arr[i]); } // Stores frequencies of array elements map<int, int, greater<int> > mp; // Update frequencies in the Map for (int i = 0; i < n; ++i) { if (arr[i] == min_ele) continue; else mp[arr[i]]++; } // Iterate the map map<int, int>::iterator it; // Stores the count of // decrements at each iteration int prev_val = 0; // Stores the total // count of decrements int ans = 0; // Calculate the number of decrements for (it = mp.begin(); it != mp.end(); ++it) { ans += (it->second + prev_val); prev_val += it->second; } // Return minimum operations return ans;}// Driver Codeint main(){ // Given array int arr[] = { 2, 5, 4, 3, 5, 4 }; // Given size int size = sizeof(arr) / sizeof(arr[0]); // Function call cout << MinimumNoOfOperations( arr, size); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class solution{ // Function to print the minimum // number of decrements to make // all elements equalsstatic int MinimumNoOfOperations(int arr[], int n){ // Find minimum element int min_ele = Integer.MAX_VALUE; for (int i = 0; i < n; ++i) { min_ele = Math.min(min_ele, arr[i]); } // Stores frequencies of array // elements TreeMap<Integer, Integer> mp = new TreeMap<Integer, Integer>( Collections.reverseOrder()); // Update frequencies in // the Map for (int i = 0; i < n; ++i) { if (arr[i] == min_ele) continue; else mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); } // Stores the count of // decrements at each // iteration int prev_val = 0; // Stores the total // count of decrements int ans = 0; // Calculate the number of // decrements for (Map.Entry<Integer, Integer> it : mp.entrySet()) { ans += (it.getValue() + prev_val); prev_val += it.getValue(); } // Return minimum operations return ans;}// Driver Codepublic static void main(String args[]){ // Given array int arr[] = {2, 5, 4, 3, 5, 4}; // Given size int size = arr.length; // Function call System.out.println( MinimumNoOfOperations(arr, size));}}// This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approachimport sys# Function to print the minimum number of# decrements to make all elements equalsdef MinimumNoOfOperations(arr, n): # Find minimum element min_ele = sys.maxsize for i in range(n): min_ele = min(min_ele, arr[i]) # Stores frequencies of array elements mp = {} # Update frequencies in the Map for i in range(n): if (arr[i] == min_ele): continue else: mp[arr[i]] = mp.get(arr[i], 0) + 1 # Stores the count of # decrements at each iteration prev_val = 0 # Stores the total # count of decrements ans = 0 # Calculate the number of decrements for it in mp: ans += (mp[it] + prev_val) prev_val += mp[it] # Return minimum operations return ans# Driver Codeif __name__ == '__main__': # Given array arr = [ 2, 5, 4, 3, 5, 4 ] # Given size size = len(arr) # Function call print(MinimumNoOfOperations(arr, size))# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System.Collections.Generic; using System;using System.Linq;class GFG{ // Function to print the minimum // number of decrements to make // all elements equalsstatic int MinimumNoOfOperations(int []arr, int n){ // Find minimum element int min_ele = 1000000000; for(int i = 0; i < n; ++i) { min_ele = Math.Min(min_ele, arr[i]); } // Stores frequencies of array // elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Update frequencies in // the Map for(int i = 0; i < n; ++i) { if (arr[i] == min_ele) continue; else { if (mp.ContainsKey(arr[i]) == true) mp[arr[i]] += 1; else mp[arr[i]] = 1; } } // Stores the count of // decrements at each // iteration int prev_val = 0; // Stores the total // count of decrements int ans = 0; // Calculate the number of // decrements var val = mp.Keys.ToList(); foreach(var key in val) { ans += (mp[key] + prev_val); prev_val += mp[key]; } // Return minimum operations return ans;}// Driver Codepublic static void Main(String[] args) { // Given array int []arr = { 2, 5, 4, 3, 5, 4 }; // Given size int size = arr.Length; // Function call Console.WriteLine(MinimumNoOfOperations( arr, size));}}// This code is contributed by Stream_Cipher |
Javascript
<script>// Javascript program for the above approach// Function to print the minimum number of// decrements to make all elements equalsfunction MinimumNoOfOperations(arr, n){ // Find minimum element var min_ele = 1000000000; for (var i = 0; i < n; ++i) { min_ele = Math.min(min_ele, arr[i]); } // Stores frequencies of array elements var mp = new Map(); // Update frequencies in the Map for (var i = 0; i < n; ++i) { if (arr[i] == min_ele) continue; else { if(mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i])+1); } else { mp.set(arr[i], 1); } } } // Stores the count of // decrements at each iteration var prev_val = 0; // Stores the total // count of decrements var ans = 0; var keys = []; mp.forEach((value, key) => { keys.push(key); }); keys.sort((a,b)=>b-a); // Calculate the number of decrements keys.forEach(value => { ans += (mp.get(value) + prev_val); prev_val += mp.get(value); }); // Return minimum operations return ans;}// Driver Code// Given arrayvar arr = [2, 5, 4, 3, 5, 4];// Given sizevar size = arr.length// Function calldocument.write( MinimumNoOfOperations( arr, size));</script> |
Output:
11
Time Complexity: O(N) where N is the size of the array.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
