Minimice las inserciones en Array para hacer la proporción de cada par como K

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*K

Por 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++ 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 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.

# 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# 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.

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