Count of pairs in an array whose product is a perfect square

0 0 11 minutes read

Given an array arr[] of N integers, the task is to find the number of pairs (arr[i], arr[j]) such that arr[i]*arr[j] is a perfect square.

Examples:

Input: arr[] = { 1, 2, 4, 8, 5, 6}
Output: 2
Explanation:
The pairs such that the product of an element is perfectly square are (1, 4) and (8, 2).

Input: arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Output: 4
Explanation:
The pairs such that the product of an element is perfectly square are (1, 4), (1, 9), (2, 8) and (4, 9).

Naive Approach:
Run two loops from 1 to n and count all the pairs (i, j) where arr[i]*arr[j] is a perfect square. The time complexity of this approach will be O(N²).

C++

// C++ code for above approach.
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if number
// is perfect square or not
bool checkperfectsquare(int n)
{
    // If ceil and floor are equal
    // the number is a perfect
    // square
    if (ceil((double)sqrt(n)) == floor((double)sqrt(n))) {
        return true;
    }
    else {
        return false;
    }
}
 
// Function that return total count
// of pairs with perfect square product
int countPairs(int arr[], int n)
{
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Checking the pair with
            // arr[i]*arr[j] as perfect square
            if (checkperfectsquare(arr[i] * arr[j])) {
                count++;
            }
        }
    }
 
    // Returning the count
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 4, 8, 5, 6 };
 
    // Size of arr[]
    int n = sizeof(arr) / sizeof(int);
 
    cout << countPairs(arr, n) << endl;
 
    return 0;
}
 
// This code is contributed by Utkarsh Kumar.

Java

// Java code for above approach.
import java.io.*;
 
class GFG {
    // Function to check if number
    // is perfect square or not
    static boolean checkperfectsquare(int n)
    {
        // If ceil and floor are equal
        // the number is a perfect
        // square
 
        if (Math.ceil((double)Math.sqrt(n))
            == Math.floor((double)Math.sqrt(n))) {
            return true;
        }
        else {
            return false;
        }
    }
 
    // Function that return total count
    // of pairs with perfect square product
    static int countPairs(int arr[], int n)
    {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Checking the pair with
                // arr[i]*arr[j] as perfect square
                if (checkperfectsquare(arr[i] * arr[j])) {
                    count++;
                }
            }
        }
 
        // Returning the count
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 4, 8, 5, 6 };
 
        // Size of arr[]
        int n = arr.length;
 
        System.out.println(countPairs(arr, n));
    }
}
 
// This code is contributed by Pushpesh Raj.

Python3

import math
 
# Function to check if number
# is perfect square or not
 
 
def checkperfectsquare(n):
    # If ceil and floor are equal
    # the number is a perfect
    # square
 
    if math.ceil(math.sqrt(n)) == math.floor(math.sqrt(n)):
        return True
    else:
        return False
 
# Function that return total count
# of pairs with perfect square product
 
 
def countPairs(arr, n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            # Checking the pair with
            # arr[i]*arr[j] as perfect square
            if checkperfectsquare(arr[i] * arr[j]):
                count += 1
 
    # Returning the count
    return count
 
 
# Driver code
if __name__ == '__main__':
    arr = [1, 2, 4, 8, 5, 6]
 
    # Size of arr[]
    n = len(arr)
 
    print(countPairs(arr, n))

Javascript

// JavaScript code for above approach.
 
// Function to check if number
// is perfect square or not
function checkperfectsquare(n) {
     
    // If ceil and floor are equal
    // the number is a perfect
    // square
    if (Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n))) {
        return true;
    } 
    else {
        return false;
    }
}
 
// Function that return total count
// of pairs with perfect square product
function countPairs(arr, n) {
     
    let count = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
             
            // Checking the pair with
            // arr[i]*arr[j] as perfect square
            if (checkperfectsquare(arr[i] * arr[j])) {
                count++;
            }
        }
    }
 
    // Returning the count
    return count;
}
 
// Driver code
let arr = [1, 2, 4, 8, 5, 6];
 
// Size of arr[]
let n = arr.length;
 
console.log(countPairs(arr, n));
// This code is contributed prasad264

C#

using System;
 
public class MainClass {
    public static bool CheckPerfectSquare(int n)
    {
        // If ceil and floor are equal
        // the number is a perfect
        // square
        if (Math.Ceiling(Math.Sqrt(n))
            == Math.Floor(Math.Sqrt(n))) {
            return true;
        }
        else {
            return false;
        }
    }
 
    public static int CountPairs(int[] arr, int n)
    {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Checking the pair with
                // arr[i]*arr[j] as perfect square
                if (CheckPerfectSquare(arr[i] * arr[j])) {
                    count += 1;
                }
            }
        }
 
        // Returning the count
        return count;
    }
 
    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 4, 8, 5, 6 };
 
        // Size of arr[]
        int n = arr.Length;
 
        Console.WriteLine(CountPairs(arr, n));
    }
}
 
// This code is contributed by shivhack999

Output

Time Complexity : O(n^2) // since two nested loops are used the time taken by the algorithm to complete all operation is quadratic.

Space Complexity : O(1) // since no extra array is used so the space taken by the algorithm is constant

Efficient Approach:
Each integer in arr[] can be represented in the following form:

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

Steps:

Represent every element in the form of equation(1).
Then, for every pair (arr[i], arr[j]) in arr[] can be represented as:

arr[i] = k_i*x;
arr[j] = k_j*y;
where x and y are perfect square

For pairs (arr[i], arr[j]), the product of arr[i] and arr[j] can be perfectly square if and only if k_i = k_j
Use Sieve of Eratosthenes to pre-compute the value of k for every element in array arr[].
Store the frequency of k for every element in arr[] in map.
Therefore, the total number of pairs is given by the number of pairs formed by elements with a frequency greater than 1.
The total number of pairs formed by n elements is given by:

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

Below is the implementation of the above approach:

C++

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

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

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

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

Javascript

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

Output:

Time Complexity: O(N*log(log N)), since sieve of Eratosthenes takes N *log(log N) time to execute
Auxiliary Space: O(N + 10⁵)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!