Count of pairs in an array whose sum is a perfect square
Given an array of distinct elements, the task is to find the total number of two element pairs from the array whose sum is a perfect square.
Examples:
Input: arr[] = {2, 3, 6, 9, 10, 20}
Output: 2 Only possible pairs are (3, 6) and (6, 10)Input: arr[] = {9, 2, 5, 1}
Output: 0
Naive Approach: Use nested loops and check every possible pair for whether their sum is a perfect square or not. This technique is not effective when the length of the array is very large.
Efficient Approach:
- Store all the elements of the array in a HashSet named nums and save the sum of the maximum two elements in a variable named max.
- It is clear that the sum of any two elements from the array will not exceed max. So, find all the perfect squares which are ? max and save it in an ArrayList named perfectSquares.
- Now for every element in the array say arr[i] and for every perfect square saved in perfectSquares, check whether perfectSquares.get(i) – arr[i] exists in nums or not i.e. if there is any element in the original array that when added with the currently chosen element gives any perfect square from the list.
- If the above condition is satisfied, increment the count variable.
- Print the value of count in the end.
Below is the implementation of the above approach:
C++
// CPP implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return an ArrayList containing // all the perfect squares upto n vector< int > getPerfectSquares( int n) { vector< int > perfectSquares; int current = 1, i = 1; // while current perfect square is less than or equal to n while (current <= n) { perfectSquares.push_back(current); current = static_cast < int >( pow (++i, 2)); } return perfectSquares; } // Function to print the sum of maximum // two elements from the array int maxPairSum(vector< int > &arr) { int n = arr.size(); int max, secondMax; if (arr[0] > arr[1]) { max = arr[0]; secondMax = arr[1]; } else { max = arr[1]; secondMax = arr[0]; } for ( int i = 2; i < n; i++) { if (arr[i] > max) { secondMax = max; max = arr[i]; } else if (arr[i] > secondMax) { secondMax = arr[i]; } } return (max + secondMax); } // Function to return the count of numbers that // when added with n give a perfect square int countPairsWith( int n, vector< int > &perfectSquares, unordered_set< int > &nums) { int count = 0; for ( int i = 0; i < perfectSquares.size(); i++) { int temp = perfectSquares[i] - n; // temp > n is checked so that pairs // (x, y) and (y, x) don't get counted twice if (temp > n && find(nums.begin(), nums.end(), temp) != nums.end()) { count++; } } return count; } // Function to count the pairs whose sum is a perfect square int countPairs(vector< int > &arr) { int i, n = arr.size(); // Sum of the maximum two elements from the array int max = maxPairSum(arr); // List of perfect squares upto max vector< int > perfectSquares = getPerfectSquares(max); // Contains all the array elements unordered_set< int > nums; for (i = 0; i < n; i++) { nums.insert(arr[i]); } int count = 0; for (i = 0; i < n; i++) { // Add count of the elements that when // added with arr[i] give a perfect square count += countPairsWith(arr[i], perfectSquares, nums); } return count; } // Driver code int main() { vector< int > arr = {2, 3, 6, 9, 10, 20}; cout << countPairs(arr) << endl; return 0; } // This code is contributed by mits |
Java
// Java implementation of the approach import java.util.*; public class GFG { // Function to return an ArrayList containing // all the perfect squares upto n public static ArrayList<Integer> getPerfectSquares( int n) { ArrayList<Integer> perfectSquares = new ArrayList<>(); int current = 1 , i = 1 ; // while current perfect square is less than or equal to n while (current <= n) { perfectSquares.add(current); current = ( int )Math.pow(++i, 2 ); } return perfectSquares; } // Function to print the sum of maximum // two elements from the array public static int maxPairSum( int arr[]) { int n = arr.length; int max, secondMax; if (arr[ 0 ] > arr[ 1 ]) { max = arr[ 0 ]; secondMax = arr[ 1 ]; } else { max = arr[ 1 ]; secondMax = arr[ 0 ]; } for ( int i = 2 ; i < n; i++) { if (arr[i] > max) { secondMax = max; max = arr[i]; } else if (arr[i] > secondMax) { secondMax = arr[i]; } } return (max + secondMax); } // Function to return the count of numbers that // when added with n give a perfect square public static int countPairsWith( int n, ArrayList<Integer> perfectSquares, HashSet<Integer> nums) { int count = 0 ; for ( int i = 0 ; i < perfectSquares.size(); i++) { int temp = perfectSquares.get(i) - n; // temp > n is checked so that pairs // (x, y) and (y, x) don't get counted twice if (temp > n && nums.contains(temp)) count++; } return count; } // Function to count the pairs whose sum is a perfect square public static int countPairs( int arr[]) { int i, n = arr.length; // Sum of the maximum two elements from the array int max = maxPairSum(arr); // List of perfect squares upto max ArrayList<Integer> perfectSquares = getPerfectSquares(max); // Contains all the array elements HashSet<Integer> nums = new HashSet<>(); for (i = 0 ; i < n; i++) nums.add(arr[i]); int count = 0 ; for (i = 0 ; i < n; i++) { // Add count of the elements that when // added with arr[i] give a perfect square count += countPairsWith(arr[i], perfectSquares, nums); } return count; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 3 , 6 , 9 , 10 , 20 }; System.out.println(countPairs(arr)); } } |
Python3
# Python3 implementation of the approach # Function to return an ArrayList containing # all the perfect squares upto n def getPerfectSquares(n): perfectSquares = []; current = 1 ; i = 1 ; # while current perfect square is # less than or equal to n while (current < = n): perfectSquares.append(current); i + = 1 ; current = int ( pow (i, 2 )); return perfectSquares; # Function to print the sum of maximum # two elements from the array def maxPairSum(arr): n = len (arr); max = 0 ; secondMax = 0 ; if (arr[ 0 ] > arr[ 1 ]): max = arr[ 0 ]; secondMax = arr[ 1 ]; else : max = arr[ 1 ]; secondMax = arr[ 0 ]; for i in range ( 2 , n): if (arr[i] > max ): secondMax = max ; max = arr[i]; elif (arr[i] > secondMax): secondMax = arr[i]; return ( max + secondMax); # Function to return the count of numbers that # when added with n give a perfect square def countPairsWith(n, perfectSquares, nums): count = 0 ; for i in range ( len (perfectSquares)): temp = perfectSquares[i] - n; # temp > n is checked so that pairs # (x, y) and (y, x) don't get counted twice if (temp > n and (temp in nums)): count + = 1 ; return count; # Function to count the pairs whose # sum is a perfect square def countPairs(arr): n = len (arr); # Sum of the maximum two elements # from the array max = maxPairSum(arr); # List of perfect squares upto max perfectSquares = getPerfectSquares( max ); # Contains all the array elements nums = []; for i in range (n): nums.append(arr[i]); count = 0 ; for i in range (n): # Add count of the elements that when # added with arr[i] give a perfect square count + = countPairsWith(arr[i], perfectSquares, nums); return count; # Driver code arr = [ 2 , 3 , 6 , 9 , 10 , 20 ]; print (countPairs(arr)); # This code is contributed by mits |
C#
// C# implementation of the approach using System; using System.Collections; using System.Collections.Generic; public class GFG { // Function to return an ArrayList containing // all the perfect squares upto n public static ArrayList getPerfectSquares( int n) { ArrayList perfectSquares = new ArrayList(); int current = 1, i = 1; // while current perfect square is less than or equal to n while (current <= n) { perfectSquares.Add(current); current = ( int )Math.Pow(++i, 2); } return perfectSquares; } // Function to print the sum of maximum // two elements from the array public static int maxPairSum( int [] arr) { int n = arr.Length; int max, secondMax; if (arr[0] > arr[1]) { max = arr[0]; secondMax = arr[1]; } else { max = arr[1]; secondMax = arr[0]; } for ( int i = 2; i < n; i++) { if (arr[i] > max) { secondMax = max; max = arr[i]; } else if (arr[i] > secondMax) { secondMax = arr[i]; } } return (max + secondMax); } // Function to return the count of numbers that // when added with n give a perfect square public static int countPairsWith( int n, ArrayList perfectSquares, ArrayList nums) { int count = 0; for ( int i = 0; i < perfectSquares.Count; i++) { int temp = ( int )perfectSquares[i] - n; // temp > n is checked so that pairs // (x, y) and (y, x) don't get counted twice if (temp > n && nums.Contains(temp)) count++; } return count; } // Function to count the pairs whose sum is a perfect square public static int countPairs( int [] arr) { int i, n = arr.Length; // Sum of the maximum two elements from the array int max = maxPairSum(arr); // List of perfect squares upto max ArrayList perfectSquares = getPerfectSquares(max); // Contains all the array elements ArrayList nums = new ArrayList(); for (i = 0; i < n; i++) nums.Add(arr[i]); int count = 0; for (i = 0; i < n; i++) { // Add count of the elements that when // added with arr[i] give a perfect square count += countPairsWith(arr[i], perfectSquares, nums); } return count; } // Driver code public static void Main() { int [] arr = { 2, 3, 6, 9, 10, 20 }; Console.WriteLine(countPairs(arr)); } } // This code is contributed by mits |
PHP
<?php // PHP implementation of the approach // Function to return an ArrayList containing // all the perfect squares upto n function getPerfectSquares( $n ) { $perfectSquares = array (); $current = 1; $i = 1; // while current perfect square // is less than or equal to n while ( $current <= $n ) { array_push ( $perfectSquares , $current ); $current = (int)pow(++ $i , 2); } return $perfectSquares ; } // Function to print the sum of maximum // two elements from the array function maxPairSum( $arr ) { $n = count ( $arr ); $max ; $secondMax ; if ( $arr [0] > $arr [1]) { $max = $arr [0]; $secondMax = $arr [1]; } else { $max = $arr [1]; $secondMax = $arr [0]; } for ( $i = 2; $i < $n ; $i ++) { if ( $arr [ $i ] > $max ) { $secondMax = $max ; $max = $arr [ $i ]; } else if ( $arr [ $i ] > $secondMax ) { $secondMax = $arr [ $i ]; } } return ( $max + $secondMax ); } // Function to return the count of numbers that // when added with n give a perfect square function countPairsWith( $n , $perfectSquares , $nums ) { $count = 0; for ( $i = 0; $i < count ( $perfectSquares ); $i ++) { $temp = $perfectSquares [ $i ] - $n ; // temp > n is checked so that pairs // (x, y) and (y, x) don't get counted twice if ( $temp > $n && in_array( $temp , $nums )) $count ++; } return $count ; } // Function to count the pairs whose // sum is a perfect square function countPairs( $arr ) { $n = count ( $arr ); // Sum of the maximum two elements // from the array $max = maxPairSum( $arr ); // List of perfect squares upto max $perfectSquares = getPerfectSquares( $max ); // Contains all the array elements $nums = array (); for ( $i = 0; $i < $n ; $i ++) array_push ( $nums , $arr [ $i ]); $count = 0; for ( $i = 0; $i < $n ; $i ++) { // Add count of the elements that when // added with arr[i] give a perfect square $count += countPairsWith( $arr [ $i ], $perfectSquares , $nums ); } return $count ; } // Driver code $arr = array ( 2, 3, 6, 9, 10, 20 ); echo countPairs( $arr ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return an ArrayList containing // all the perfect squares upto n function getPerfectSquares(n) { let perfectSquares = []; let current = 1; let i = 1; // while current perfect square // is less than or equal to n while (current <= n) { perfectSquares.push(current); current = Math.pow(++i, 2); } return perfectSquares; } // Function to print the sum of maximum // two elements from the array function maxPairSum(arr) { let n = arr.length let max; let secondMax; if (arr[0] > arr[1]) { max = arr[0]; secondMax = arr[1]; } else { max = arr[1]; secondMax = arr[0]; } for (let i = 2; i < n; i++) { if (arr[i] > max) { secondMax = max; max = arr[i]; } else if (arr[i] > secondMax) { secondMax = arr[$i]; } } return (max + secondMax); } // Function to return the count of numbers that // when added with n give a perfect square function countPairsWith(n, perfectSquares, nums) { let count = 0; for (let i = 0; i < perfectSquares.length; i++) { let temp = perfectSquares[i] - n; // temp > n is checked so that pairs // (x, y) and (y, x) don't get counted twice if (temp > n && nums.includes(temp)) count++; } return count; } // Function to count the pairs whose // sum is a perfect square function countPairs(arr) { let n = arr.length // Sum of the maximum two elements // from the array let max = maxPairSum(arr); // List of perfect squares upto max let perfectSquares = getPerfectSquares(max); // Contains all the array elements let nums = []; for (let i = 0; i < n; i++) nums.push(arr[i]); let count = 0; for (let i = 0; i < n; i++) { // Add count of the elements that when // added with arr[i] give a perfect square count += countPairsWith(arr[i], perfectSquares, nums); } return count; } // Driver code let arr = new Array( 2, 3, 6, 9, 10, 20 ); document.write(countPairs(arr)); // This code is contributed by Saurabh jaiswal </script> |
Output
2
Time Complexity: O(n*sqrt(max))
Auxiliary Space: O(n + sqrt(max))