Dada una array arr[] que consta de N enteros, la tarea es minimizar el número de operaciones necesarias para igualar todos los elementos de la array convirtiendo A i en A i / 2. en cada operación
Ejemplos:
Entrada: arr[] = {3, 1, 1, 3}
Salida: 2
Explicación:
Reducir A 0 a A 0 / 2 modifica arr[] a {1, 1, 1, 3}.
Reducir A 3 a A 3 / 2 modifica arr[] a {1, 1, 1, 1}.
Por lo tanto, todos los elementos de la array son iguales. Por lo tanto, las operaciones mínimas requeridas son 2.Entrada: arr[] = {2, 2, 2}
Salida: 0
Enfoque: La idea para resolver este problema es utilizar el enfoque codicioso . A continuación se muestran los pasos:
- Inicialice un mapa auxiliar , digamos mp.
- Recorra la array y, para cada elemento de la array, divida el elemento por 2 hasta que se reduzca a 1 y almacene el número resultante en el Mapa .
- Recorra el mapa y encuentre el elemento máximo que tenga una frecuencia igual a N , digamos mx .
- Nuevamente, recorra la array y, para cada elemento, divida el elemento por 2 hasta que sea igual a mx e incremente la cuenta.
- Imprima el conteo como el número mínimo de operaciones requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum number of operations int 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 Code int 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 approach import 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 operations def 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 array arr = [ 3, 1, 1, 3 ] # Size of the array N = len(arr) minOperations(arr, N) # This code is contributed by rohitsingh07052.
C#
// C# program for the above approach using 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 operations function 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 array var arr = [3, 1, 1, 3]; // Size of the array var N = arr.length; minOperations(arr, N); </script>
2
Complejidad de tiempo: O(N * log(max(arr[i]))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA