Dada una array arr[] de longitud N , la tarea es encontrar el número mínimo de elementos que se agregarán en la array de modo que exista cada par independiente en la array cuya relación sea K.
Ejemplos:
Entrada: arr[] = {1, 2, 2, 2, 4, 7}, K = 2
Salida: 2
Explicación : se pueden agregar 4, 14 para hacer que la array sea {1, 2, 2, 2, 4, 7, 4, 14}
Por lo tanto, si hacemos pares independientes como {1, 2}, {2, 4}, {2, 4} y {7, 14}, la razón de cada uno es K (=2).Entrada: arr[] = {5, 2, 3, 5, 15}, K = 3
Salida: 3
Enfoque: el problema anterior se puede resolver utilizando una técnica codiciosa y de hashing , según la siguiente observación:
Dado que se da que la razón de los pares debe ser K,
Si los dos elementos se hacen par con relación K son a y b, entonces
=> a/b = K
=> a = b*K
=> Los dos elementos serán siempre b y b*KPor lo tanto, para que la razón de a y b sea K, b y b*K deben estar presentes en la array.
Entonces, en el Array, para cada elemento arr[i],
- necesitamos verificar si arr[i] * K está presente en esa array .
- Si está presente, que sea un par.
- De lo contrario, agregue el arr[i] * K a la array
Siga estos pasos para resolver el problema anterior:
- Inicialice un hashmap m para almacenar las frecuencias de los elementos en la array.
- Atraviesa la array y almacena las frecuencias
- Ordene la array arr[].
- Inicialice cnt_pairs para almacenar el recuento de los pares disponibles con la ración k.
- Recorra la array ordenada y verifique el elemento de emparejamiento.
- Compruebe si el par con la relación k está presente para arr[i], considérelos como un par y elimínelos del hashmap disminuyendo las frecuencias.
- Realice un seguimiento de los pares disponibles en la variable cnt_pairs incrementándola en 2.
- Imprima los elementos individuales restando cnt_pairs de n.
A continuación se muestra la implementación del enfoque anterior :
C++
// C++ program to minimize insertions in // Array to make ratio of each pair as K #include <bits/stdc++.h> using namespace std; // Function to minimize insertions // in Array to make ratio // of each pair as K int find_min_additions( int arr[], int n, int x) { // Initialize a hashmap // and store the frequencies // of the array elements unordered_map<int, int> m; // Traverse the array // and store the frequencies for (int i = 0; i < n; i++) { m[arr[i]]++; } // sort the array sort(arr, arr + n); // Initialize the cnt_pairs to store the // count of the available pairs int cnt_pairs = 0; for (int i = 0; i < n; ++i) { // Check if the pair with ratio k is // present for arr[i] if (m[arr[i] * x] > 0 && m[arr[i]] > 0) { // Consider them as a pair // and remove from the hashmap m[arr[i] * x]--; m[arr[i]]--; // Add the count of the pairs cnt_pairs += 2; } } // Return the count of single elements // that need another element // to make ratio k return n - cnt_pairs; } // Driver code int main() { int arr[] = { 1, 2, 2, 2, 4, 7 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 2; cout << find_min_additions(arr, n, K); }
Java
// Java program to minimize insertions in // Array to make ratio of each pair as K import java.util.*; class GFG{ // Function to minimize insertions // in Array to make ratio // of each pair as K static int find_min_additions( int []arr, int n, int x) { // Initialize a hashmap // and store the frequencies // of the array elements HashMap<Integer, Integer> m = new HashMap<>(); // Traverse the array // and store the frequencies for (int i = 0; i < n; i++) { int c = 0; if(m.containsKey(arr[i])) { c = m.get(arr[i]); } m.put(arr[i], c + 1); } // sort the array Arrays.sort(arr); // Initialize the cnt_pairs to store the // count of the available pairs int cnt_pairs = 0; for (int i = 0; i < n; ++i) { // Check if the pair with ratio k is // present for arr[i] if (m.containsKey(arr[i] * x) && m.get(arr[i] * x) > 0 && m.get(arr[i]) > 0) { // Consider them as a pair // and remove from the hashmap m.put(arr[i] * x, m.get(arr[i] * x) - 1); m.put(arr[i], m.get(arr[i]) - 1); // Add the count of the pairs cnt_pairs += 2; } } // Return the count of single elements // that need another element // to make ratio k return n - cnt_pairs; } // Driver code public static void main (String[] args) { int arr[] = { 1, 2, 2, 2, 4, 7 }; int n = arr.length; int K = 2; System.out.print(find_min_additions(arr, n, K)); } } // This code is contributed by hrithikgarg03188.
Python3
# Python program to minimize insertions in # Array to make ratio of each pair as K # Function to minimize insertions # in Array to make ratio # of each pair as K def find_min_additions(arr, n, x): # Initialize a hashmap # and store the frequencies # of the array elements m = {} # Traverse the array # and store the frequencies for i in range(0, n): m[arr[i]] = m[arr[i]] + 1 if arr[i] in m else 1 # sort the array arr.sort() # Initialize the cnt_pairs to store the # count of the available pairs cnt_pairs = 0 for i in range(0, n): # Check if the pair with ratio k is # present for arr[i] if (arr[i] * x in m and arr[i] in m and m[arr[i] * x] > 0 and m[arr[i]] > 0): # Consider them as a pair # and remove from the hashmap m[arr[i] * x] -= 1 m[arr[i]] -= 1 # Add the count of the pairs cnt_pairs += 2 # Return the count of single elements # that need another element # to make ratio k return n - cnt_pairs # Driver code if __name__ == "__main__": arr = [1, 2, 2, 2, 4, 7] n = len(arr) K = 2 print(find_min_additions(arr, n, K)) # This code is contributed by rakeshsahni
C#
// C# program to minimize insertions in // Array to make ratio of each pair as K using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to minimize insertions // in Array to make ratio // of each pair as K static int find_min_additions( int []arr, int n, int x) { // Initialize a hashmap // and store the frequencies // of the array elements Dictionary<int, int> m = new Dictionary<int, int>(); // Traverse the array // and store the frequencies for (int i = 0; i < n; i++) { int c = 0; if(m.ContainsKey(arr[i])) { c = m[arr[i]]; } m[arr[i]] = c + 1; } // sort the array Array.Sort(arr); // Initialize the cnt_pairs to store the // count of the available pairs int cnt_pairs = 0; for (int i = 0; i < n; ++i) { // Check if the pair with ratio k is // present for arr[i] if (m.ContainsKey(arr[i] * x) && m[arr[i] * x] > 0 && m[arr[i]] > 0) { // Consider them as a pair // and remove from the hashmap m[arr[i] * x]--; m[arr[i]]--; // Add the count of the pairs cnt_pairs += 2; } } // Return the count of single elements // that need another element // to make ratio k return n - cnt_pairs; } // Driver code public static void Main() { int []arr = { 1, 2, 2, 2, 4, 7 }; int n = arr.Length; int K = 2; Console.Write(find_min_additions(arr, n, K)); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript program to minimize insertions in // Array to make ratio of each pair as K // Function to minimize insertions // in Array to make ratio // of each pair as K const find_min_additions = (arr, n, x) => { // Initialize a hashmap // and store the frequencies // of the array elements let m = {}; // Traverse the array // and store the frequencies for (let i = 0; i < n; i++) { arr[i] in m ? m[arr[i]] += 1 : m[arr[i]] = 1; } // sort the array arr.sort(); // Initialize the cnt_pairs to store the // count of the available pairs let cnt_pairs = 0; for (let i = 0; i < n; ++i) { // Check if the pair with ratio k is // present for arr[i] if ((arr[i] * x) in m && arr[i] in m) { if (m[arr[i] * x] > 0 && m[arr[i]] > 0) { // Consider them as a pair // and remove from the hashmap m[arr[i] * x] -= 1; m[arr[i]] -= 1; // Add the count of the pairs cnt_pairs += 2; } } } // Return the count of single elements // that need another element // to make ratio k return n - cnt_pairs; } // Driver code let arr = [1, 2, 2, 2, 4, 7]; let n = arr.length; let K = 2; document.write(find_min_additions(arr, n, K)); // This code is contributed by rakeshsahni </script>
2
Complejidad de tiempo: O(N*log N) donde N es el tamaño de la array.
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA