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(N2).
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 |
2
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] = ki*x; arr[j] = kj*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 ki = kj
- 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> |
2
Time Complexity: O(N*log(log N)), since sieve of Eratosthenes takes N *log(log N) time to execute
Auxiliary Space: O(N + 105)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!