Cuente todos los pares posibles en el Array dado con el producto K

arr[] N K a

Ejemplos:

Entrada: arr[] = {1, 2, 16, 4, 4, 4, 8 }, K=16
Salida: 5
Explicación : los pares posibles son (1, 16), (2, 8), (4, 4) , (4, 4), (4, 4)

Entrada: arr[] = {1, 10, 20, 10, 4, 5, 5, 2 }, K=20
Salida: 5
Explicación : Los pares posibles son (1, 20), (2, 10), (2, 10), (4, 5), (4, 5)

Enfoque: la idea es usar hashing para almacenar los elementos y verificar si K/arr[i] existe en la array o no usa el mapa y aumentar el conteo en consecuencia. 

Siga los pasos a continuación para resolver el problema:

• Inicialice la variable count como 0 para almacenar la respuesta.
• Inicialice unordered_map<int, int> mp[] .
• Itere sobre el rango [0, N) usando la variable i y almacene las frecuencias de todos los elementos de la array arr[] en el mapa mp[].
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Inicialice el índice de la variable como K/arr[i] .
  • Si K no es una potencia de 2 y el índice está presente en el mapa mp[] , aumente el valor de count en mp[arr[i]]*mp[index] y borre ambos del mapa mp[].
  • Si K es una potencia de 2 y el índice está presente en el mapa mp[] , aumente el valor de cuenta en mp[índice]*(mp[índice]-1)/2 y bórrelo del mapa mp[].
• Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count
// the total number of pairs
int countPairsWithProductK(
    int arr[], int n, int k)
 
{
 
    int count = 0;
 
    // Initialize hashmap.
    unordered_map<int, int> mp;
 
    // Insert array elements to hashmap
    for (int i = 0; i < n; i++) {
 
        mp[arr[i]]++;
    }
 
    for (int i = 0; i < n; i++) {
 
        double index = 1.0 * k / arr[i];
 
        // If k is not power of two
        if (index >= 0
            && ((index - (int)(index)) == 0)
            && mp.find(k / arr[i]) != mp.end()
            && (index != arr[i])) {
 
            count += mp[arr[i]] * mp[index];
 
            // After counting erase the element
            mp.erase(arr[i]);
 
            mp.erase(index);
        }
 
        // If k is power of 2
        if (index >= 0
            && ((index - (int)(index)) == 0)
            && mp.find(k / arr[i]) != mp.end()
            && (index == arr[i])) {
 
            // Pair count
            count += (mp[arr[i]]
                      * (mp[arr[i]] - 1))
                     / 2;
 
            // After counting erase the element;
            mp.erase(arr[i]);
        }
    }
 
    return count;
}
 
// Driver Code
int main()
 
{
 
    int arr[] = { 1, 2, 16, 4, 4, 4, 8 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int K = 16;
 
    cout << countPairsWithProductK(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
  // Function to count
  // the total number of pairs
  static int countPairsWithProductK(
    int arr[], int n, int k)
 
  {
 
    int count = 0;
 
    // Initialize hashmap.
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
 
    // Insert array elements to hashmap
    for (int i = 0; i < n; i++) {
 
      if(mp.containsKey(arr[i])){
        mp.put(arr[i], mp.get(arr[i])+1);
      }else{
        mp.put(arr[i], 1);
      }
    }
 
    for (int i = 0; i < n; i++) {
 
      int index = (int) (1.0 * k / arr[i]);
 
      // If k is not power of two
      if (index >= 0
          && ((index - (int)(index)) == 0)
          && mp.containsKey(k / arr[i])
          && (index != arr[i])) {
 
        count += mp.get(arr[i]) * mp.get(index);
 
        // After counting erase the element
        mp.remove(arr[i]);
 
        mp.remove(index);
      }
 
      // If k is power of 2
      if (index >= 0
          && ((index - (int)(index)) == 0)
          && mp.containsKey(k / arr[i])
          && (index == arr[i])) {
 
        // Pair count
        count += (mp.get(arr[i])
                  * (mp.get(arr[i]) - 1))
          / 2;
 
        // After counting erase the element;
        mp.remove(arr[i]);
      }
    }
 
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int arr[] = { 1, 2, 16, 4, 4, 4, 8 };
    int N = arr.length;
    int K = 16;
    System.out.print(countPairsWithProductK(arr, N, K));
 
  }
}
 
// This code is contributed by 29AjayKumar

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to count
# the total number of pairs
def countPairsWithProductK(arr, n, k):
 
    count = 0
 
    # Initialize hashmap.
    mp = defaultdict(int)
 
    # Insert array elements to hashmap
    for i in range(n):
 
        mp[arr[i]] += 1
 
    for i in range(n):
 
        index = 1.0 * k / arr[i]
 
        # If k is not power of two
        if (index >= 0
            and ((index - (int)(index)) == 0)
            and (k / arr[i]) in mp
                and (index != arr[i])):
 
            count += mp[arr[i]] * mp[index]
 
            # After counting erase the element
            del mp[arr[i]]
 
            del mp[index]
 
        # If k is power of 2
        if (index >= 0
            and ((index - (int)(index)) == 0)
            and (k / arr[i]) in mp
                and (index == arr[i])):
 
            # Pair count
            count += ((mp[arr[i]]
                       * (mp[arr[i]] - 1)) / 2)
 
            # After counting erase the element;
            del mp[arr[i]]
 
    return count
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 16, 4, 4, 4, 8]
 
    N = len(arr)
 
    K = 16
 
    print(int(countPairsWithProductK(arr, N, K)))
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to count
  // the total number of pairs
  static int countPairsWithProductK(
    int []arr, int n, int k)
 
  {
 
    int count = 0;
 
    // Initialize hashmap.
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Insert array elements to hashmap
    for (int i = 0; i < n; i++) {
 
      if(mp.ContainsKey(arr[i])){
        mp[arr[i]] = mp[arr[i]]+1;
      }else{
        mp.Add(arr[i], 1);
      }
    }
 
    for (int i = 0; i < n; i++) {
 
      int index = (int) (1.0 * k / arr[i]);
 
      // If k is not power of two
      if (index >= 0
          && ((index - (int)(index)) == 0)
          && mp.ContainsKey(k / arr[i])
          && (index != arr[i])) {
 
        count += mp[arr[i]] * mp[index];
 
        // After counting erase the element
        mp.Remove(arr[i]);
 
        mp.Remove(index);
      }
 
      // If k is power of 2
      if (index >= 0
          && ((index - (int)(index)) == 0)
          && mp.ContainsKey(k / arr[i])
          && (index == arr[i])) {
 
        // Pair count
        count += (mp[arr[i]]
                  * (mp[arr[i]] - 1))
          / 2;
 
        // After counting erase the element;
        mp.Remove(arr[i]);
      }
    }
 
    return count;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    int []arr = { 1, 2, 16, 4, 4, 4, 8 };
    int N = arr.Length;
    int K = 16;
    Console.Write(countPairsWithProductK(arr, N, K));
 
  }
}
 
// This code is contributed by Rajput-Ji

<script>
      // JavaScript code for the above approach
      // Function to count
      // the total number of pairs
      function countPairsWithProductK(
          arr, n, k) {
 
          let count = 0;
 
          // Initialize hashmap.
          let mp = new Map();
 
          // Insert array elements to hashmap
          for (let i = 0; i < n; i++) {
 
              if (mp.has(arr[i])) {
                  mp.set(arr[i], mp.get(arr[i]) + 1);
              }
              else {
                  mp.set(arr[i], 1);
              }
          }
 
          for (let i = 0; i < n; i++) {
 
              let index = 1.0 * k / arr[i];
 
              // If k is not power of two
              if (index >= 0
                  && ((index - Math.floor(index)) == 0)
                  && mp.has(k / arr[i])
                  && (index != arr[i])) {
 
                  count += mp.get(arr[i]) * mp.get(index);
 
                  // After counting erase the element
                  mp.delete(arr[i]);
 
                  mp.delete(index);
              }
 
              // If k is power of 2
              if (index >= 0
                  && ((index - Math.floor(index)) == 0)
                  && mp.has(k / arr[i])
                  && (index == arr[i])) {
 
                  // Pair count
                  count += (mp.get(arr[i])
                      * (mp.get(arr[i]) - 1))
                      / 2;
 
                  // After counting erase the element;
                  mp.delete(arr[i]);
              }
          }
 
          return count;
      }
 
      // Driver Code
      let arr = [1, 2, 16, 4, 4, 4, 8];
      let N = arr.length;
      let K = 16;
      document.write(countPairsWithProductK(arr, N, K));
 
     // This code is contributed by Potta Lokesh
  </script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(N)