Conteo de pares en una array cuyo producto es un cuadrado perfecto

Dada una array arr[] de N enteros, la tarea es encontrar el número de pares (arr[i], arr[j]) tales que arr[i]*arr[j] sea un cuadrado perfecto. 

Ejemplos:  

Entrada: arr[] = { 1, 2, 4, 8, 5, 6} 
Salida: 2 
Explicación: 
Los pares tales que el producto de un elemento es perfectamente cuadrado son (1, 4) y (8, 2).

Entrada: arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } 
Salida: 4 
Explicación: 
Los pares tales que el producto de un elemento es perfectamente cuadrado son (1, 4), ( 1, 9), (2, 8) y (4, 9). 

Enfoque ingenuo: 
ejecute dos bucles de 1 a n y cuente todos los pares (i, j) donde arr[i]*arr[j] es un cuadrado perfecto. La complejidad temporal de este enfoque será O(N ² ) .

Enfoque eficiente: 
cada número entero en arr[] se puede representar de la siguiente forma:

arr[i] = k*x          ..............(1)
where k is not divisible by any perfect square other than 1,
and x = perfect square,

Pasos:  

• Representa cada elemento en la forma de la ecuación (1).
• Entonces, para cada par (arr[i], arr[j]) en arr[] se puede representar como:

arr[i] = ki*x;
arr[j] = kj*y;
where x and y are perfect square

• Para pares (arr[i], arr[j]) , el producto de arr[i] y arr[j] puede ser perfectamente cuadrado si y solo si k _i = k _j
• Use Sieve of Eratosthenes para precalcular el valor de k para cada elemento en el arreglo arr[] .
• Almacene la frecuencia de k para cada elemento en arr[] en map .
• Por lo tanto, el número total de pares viene dado por el número de pares formados por elementos con una frecuencia mayor que 1.
• El número total de parejas formadas por n elementos viene dado por:

Number of Pairs = (f*(f-1))/2
where f is the frequency of an element.

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

// C++ program to calculate the number of
// pairs with product is perfect square
#include <bits/stdc++.h>
using namespace std;
 
// Prime[] array to calculate Prime Number
int prime[100001] = { 0 };
 
// Array k[] to store the value of k for
// each element in arr[]
int k[100001] = { 0 };
 
// For value of k, Sieve function is
// implemented
void Sieve()
{
    // Initialize k[i] to i
    for (int i = 1; i < 100001; i++)
        k[i] = i;
 
    // Prime Sieve
    for (int i = 2; i < 100001; i++) {
 
        // If i is prime then remove all
        // factors of prime from it
        if (prime[i] == 0)
            for (int j = i; j < 100001; j += i) {
 
                // Update that j is not
                // prime
                prime[j] = 1;
 
                // Remove all square divisors
                // i.e. if k[j] is divisible
                // by i*i then divide it by i*i
                while (k[j] % (i * i) == 0)
                    k[j] /= (i * i);
            }
    }
}
 
// Function that return total count
// of pairs with perfect square product
int countPairs(int arr[], int n)
{
    // Map used to store the frequency of k
    unordered_map<int, int> freq;
 
    // Store the frequency of k
    for (int i = 0; i < n; i++) {
        freq[k[arr[i]]]++;
    }
 
    int sum = 0;
 
    // The total number of pairs is the
    // summation of (fi * (fi - 1))/2
    for (auto i : freq) {
        sum += ((i.second - 1) * i.second) / 2;
    }
 
    return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 4, 8, 5, 6 };
 
    // Size of arr[]
    int n = sizeof(arr) / sizeof(int);
 
    // To pre-compute the value of k
    Sieve();
 
    // Function that return total count
    // of pairs with perfect square product
    cout << countPairs(arr, n) << endl;
 
    return 0;
}

// Java program to calculate the number of
// pairs with product is perfect square
import java.util.*;
 
class GFG{
  
// Prime[] array to calculate Prime Number
static int []prime = new int[100001];
  
// Array k[] to store the value of k for
// each element in arr[]
static int []k = new int[100001];
  
// For value of k, Sieve function is
// implemented
static void Sieve()
{
    // Initialize k[i] to i
    for (int i = 1; i < 100001; i++)
        k[i] = i;
  
    // Prime Sieve
    for (int i = 2; i < 100001; i++) {
  
        // If i is prime then remove all
        // factors of prime from it
        if (prime[i] == 0)
            for (int j = i; j < 100001; j += i) {
  
                // Update that j is not
                // prime
                prime[j] = 1;
  
                // Remove all square divisors
                // i.e. if k[j] is divisible
                // by i*i then divide it by i*i
                while (k[j] % (i * i) == 0)
                    k[j] /= (i * i);
            }
    }
}
  
// Function that return total count
// of pairs with perfect square product
static int countPairs(int arr[], int n)
{
    // Map used to store the frequency of k
    HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
  
    // Store the frequency of k
    for (int i = 0; i < n; i++) {
        if(freq.containsKey(k[arr[i]])) {
            freq.put(k[arr[i]], freq.get(k[arr[i]])+1);
        }
        else
            freq.put(k[arr[i]], 1);
    }
  
    int sum = 0;
  
    // The total number of pairs is the
    // summation of (fi * (fi - 1))/2
    for (Map.Entry<Integer,Integer> i : freq.entrySet()){
        sum += ((i.getValue() - 1) * i.getValue()) / 2;
    }
  
    return sum;
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 4, 8, 5, 6 };
  
    // Size of arr[]
    int n = arr.length;
  
    // To pre-compute the value of k
    Sieve();
  
    // Function that return total count
    // of pairs with perfect square product
    System.out.print(countPairs(arr, n) +"\n");
  
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to calculate the number 
# of pairs with product is perfect square
 
# prime[] array to calculate Prime Number
prime = [0] * 100001
 
# Array to store the value of k
# for each element in arr[]
k = [0] * 100001
 
# For value of k, Sieve implemented
def Sieve():
 
    # Initialize k[i] to i
    for i in range(1, 100001):
        k[i] = i
 
    # Prime sieve
    for i in range(2, 100001):
 
        # If i is prime then remove all
        # factors of prime from it
        if (prime[i] == 0):
            for j in range(i, 100001, i):
 
                # Update that j is not prime
                prime[j] = 1
 
                # Remove all square divisors
                # i.e if k[j] is divisible by
                # i*i then divide it by i*i
                while (k[j] % (i * i) == 0):
                    k[j] /= (i * i)
 
# Function that return total count of
# pairs with perfect square product
def countPairs (arr, n):
 
    # Store the frequency of k
    freq = dict()
 
    for i in range(n):
        if k[arr[i]] in freq.keys():
            freq[k[arr[i]]] += 1
        else:
            freq[k[arr[i]]] = 1
 
    Sum = 0
 
    # The total number of pairs is the
    # summation of (fi * (fi - 1))/2
    for i in freq:
        Sum += (freq[i] * (freq[i] - 1)) / 2
 
    return Sum
 
# Driver code
arr = [ 1, 2, 4, 8, 5, 6 ]
 
# Length of arr
n = len(arr)
 
# To pre-compute the value of k
Sieve()
 
# Function that return total count
# of pairs with perfect square product
print(int(countPairs(arr, n)))
 
# This code is contributed by himanshu77

// C# program to calculate the number of
// pairs with product is perfect square
using System;
using System.Collections.Generic;
 
class GFG{
   
// Prime[] array to calculate Prime Number
static int []prime = new int[100001];
   
// Array k[] to store the value of k for
// each element in []arr
static int []k = new int[100001];
   
// For value of k, Sieve function is
// implemented
static void Sieve()
{
    // Initialize k[i] to i
    for (int i = 1; i < 100001; i++)
        k[i] = i;
   
    // Prime Sieve
    for (int i = 2; i < 100001; i++) {
   
        // If i is prime then remove all
        // factors of prime from it
        if (prime[i] == 0)
            for (int j = i; j < 100001; j += i) {
   
                // Update that j is not
                // prime
                prime[j] = 1;
   
                // Remove all square divisors
                // i.e. if k[j] is divisible
                // by i*i then divide it by i*i
                while (k[j] % (i * i) == 0)
                    k[j] /= (i * i);
            }
    }
}
   
// Function that return total count
// of pairs with perfect square product
static int countPairs(int []arr, int n)
{
    // Map used to store the frequency of k
    Dictionary<int,int> freq = new Dictionary<int,int>();
   
    // Store the frequency of k
    for (int i = 0; i < n; i++) {
        if(freq.ContainsKey(k[arr[i]])) {
            freq[k[arr[i]]] = freq[k[arr[i]]]+1;
        }
        else
            freq.Add(k[arr[i]], 1);
    }
   
    int sum = 0;
   
    // The total number of pairs is the
    // summation of (fi * (fi - 1))/2
    foreach (KeyValuePair<int,int> i in freq){
        sum += ((i.Value - 1) * i.Value) / 2;
    }
   
    return sum;
}
   
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 4, 8, 5, 6 };
   
    // Size of []arr
    int n = arr.Length;
   
    // To pre-compute the value of k
    Sieve();
   
    // Function that return total count
    // of pairs with perfect square product
    Console.Write(countPairs(arr, n) +"\n"); 
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript program to calculate the number of
// pairs with product is perfect square
 
// Prime[] array to calculate Prime Number
let prime = new Array(100001).fill(0);
 
// Array k[] to store the value of k for
// each element in arr[]
let k = new Array(100001).fill(0);
 
// For value of k, Sieve function is
// implemented
function Sieve()
{
    // Initialize k[i] to i
    for (let i = 1; i < 100001; i++)
        k[i] = i;
 
    // Prime Sieve
    for (let i = 2; i < 100001; i++) {
 
        // If i is prime then remove all
        // factors of prime from it
        if (prime[i] == 0)
            for (let j = i; j < 100001; j += i) {
 
                // Update that j is not
                // prime
                prime[j] = 1;
 
                // Remove all square divisors
                // i.e. if k[j] is divisible
                // by i*i then divide it by i*i
                while (k[j] % (i * i) == 0)
                    k[j] /= (i * i);
            }
    }
}
 
// Function that return total count
// of pairs with perfect square product
function countPairs(arr, n)
{
    // Map used to store the frequency of k
    let freq = new Map();
 
    // Store the frequency of k
    for (let i = 0; i < n; i++) {
        if(freq.has(k[arr[i]])) {
            freq.set(k[arr[i]], freq.get(k[arr[i]])+1);
        }
        else
            freq.set(k[arr[i]], 1);
    }
 
    let sum = 0;
 
    // The total number of pairs is the
    // summation of (fi * (fi - 1))/2
    for (let i of freq) {
        sum += ((i[1] - 1) * i[1]) / 2;
    }
 
    return sum;
}
 
// Driver code
 
let arr = [ 1, 2, 4, 8, 5, 6 ];
 
// Size of arr[]
let n = arr.length;
 
// To pre-compute the value of k
Sieve();
 
// Function that return total count
// of pairs with perfect square product
document.write(countPairs(arr, n) + "<br>");
 
 
// This code is contributed by _saurabh_jaiswal
</script>

2

Complejidad del tiempo: O(N*log(log N))

Espacio Auxiliar: O(N + 10 ⁵ )