Given an array arr[] consisting of N integers, the task is to minimize the number of operations required to make all array elements equal by converting Ai to Ai / 2. in each operation
Examples:
Input: arr[] = {3, 1, 1, 3}
Output: 2
Explanation:
Reducing A0 to A0 / 2 modifies arr[] to {1, 1, 1, 3}.
Reducing A3 to A3 / 2 modifies arr[] to {1, 1, 1, 1}.
Therefore, all array elements are equal, Hence, the minimum operations required is 2.Input: arr[] = {2, 2, 2}
Output: 0
Approach: The idea to solve this problem is to use Greedy Approach. Below are the steps:
- Initialize an auxiliary Map, say mp.
- Traverse the array and for each array element, divide the element by 2 until it reduces to 1, and store the resulting number in the Map.
- Traverse the map and find the maximum element having a frequency equal to N, say mx.
- Again, traverse the array and for each element, divide the element by 2 until it becomes equal to mx and increment count.
- Print count as the minimum number of required 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 find minimum number of operationsint minOperations(int arr[], int N){ // Initialize map map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { int res = arr[i]; // Divide current array // element until it reduces to 1 while (res) { mp[res]++; res /= 2; } } int mx = 1; // Traverse the map for (auto it : mp) { // Find the maximum element // having frequency equal to N if (it.second == N) { mx = it.first; } } // Stores the minimum number // of operations required int ans = 0; for (int i = 0; i < N; i++) { int res = arr[i]; // Count operations required to // convert current element to mx while (res != mx) { ans++; res /= 2; } } // Print the answer cout << ans;}// Driver Codeint main(){ // Given array int arr[] = { 3, 1, 1, 3 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); minOperations(arr, N);} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG{ // Function to find minimum number of operations static void minOperations(int[] arr, int N) { // Initialize map HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array for (int i = 0; i < N; i++) { int res = arr[i]; // Divide current array // element until it reduces to 1 if (mp.containsKey(res)) mp.put(res, mp.get(res) + 1); else mp.put(res, 1); res /= 2; } int mx = 1; for(Map.Entry<Integer, Integer> it : mp.entrySet()) { // Find the maximum element // having frequency equal to N if (it.getValue() == N) { mx = it.getKey(); } } // Stores the minimum number // of operations required int ans = 0; for (int i = 0; i < N; i++) { int res = arr[i]; // Count operations required to // convert current element to mx while (res != mx) { ans++; res /= 2; } } // Print the answer System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 3, 1, 1, 3 }; // Size of the array int N = arr.length; minOperations(arr, N); }}// This code is contributed by code_hunt. |
Python3
# Python program for the above approach# Function to find minimum number of operationsdef minOperations(arr, N): # Initialize map mp = {} # Traverse the array for i in range(N): res = arr[i] # Divide current array # element until it reduces to 1 while (res): if res in mp: mp[res] += 1 else: mp[res] = 1 res //= 2 mx = 1 # Traverse the map for it in mp: # Find the maximum element # having frequency equal to N if (mp[it] == N): mx = it # Stores the minimum number # of operations required ans = 0 for i in range(N): res = arr[i] # Count operations required to # convert current element to mx while (res != mx): ans += 1 res //= 2 # Print the answer print(ans)# Driver Code# Given arrayarr = [ 3, 1, 1, 3 ]# Size of the arrayN = len(arr)minOperations(arr, N)# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find minimum number of operations static void minOperations(int[] arr, int N) { // Initialize map Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < N; i++) { int res = arr[i]; // Divide current array // element until it reduces to 1 while (res > 0) { if(mp.ContainsKey(res)) { mp[res]++; } else{ mp[res] = 1; } res /= 2; } } int mx = 1; foreach(KeyValuePair<int, int> it in mp) { // Find the maximum element // having frequency equal to N if (it.Value == N) { mx = it.Key; } } // Stores the minimum number // of operations required int ans = 0; for (int i = 0; i < N; i++) { int res = arr[i]; // Count operations required to // convert current element to mx while (res != mx) { ans++; res /= 2; } } // Print the answer Console.Write(ans); } // Driver code static void Main() { // Given array int[] arr = { 3, 1, 1, 3 }; // Size of the array int N = arr.Length; minOperations(arr, N); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript program for the above approach// Function to find minimum number of operationsfunction minOperations(arr, N){ // Initialize map var mp = new Map(); // Traverse the array for (var i = 0; i < N; i++) { var res = arr[i]; // Divide current array // element until it reduces to 1 while (res) { if(mp.has(res)) { mp.set(res, mp.get(res)+1); } else { mp.set(res, 1); } res = parseInt(res/2); } } var mx = 1; // Traverse the map mp.forEach((value, key) => { // Find the maximum element // having frequency equal to N if (value == N) { mx = key; } }); // Stores the minimum number // of operations required var ans = 0; for (var i = 0; i < N; i++) { var res = arr[i]; // Count operations required to // convert current element to mx while (res != mx) { ans++; res = parseInt(res/2); } } // Print the answer document.write( ans);}// Driver Code// Given arrayvar arr = [3, 1, 1, 3];// Size of the arrayvar N = arr.length;minOperations(arr, N);</script> |
Output:
2
Time Complexity: O(N * log(max(arr[i]))
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!
