Count of pairs in an array whose sum is a perfect square | CPP implementation of the approach ; Function to return an ArrayList containing all the perfect squares upto n ; while current perfect square is less than or equal to n ; Function to print the sum of maximum two elements from the array ; Function to return the count of numbers that when added with n give a perfect square ; temp > n is checked so that pairs ( x , y ) and ( y , x ) don 't get counted twice  ; Function to count the pairs whose sum is a perfect square ; Sum of the maximum two elements from the array ; List of perfect squares upto max ; Contains all the array elements ; Add count of the elements that when added with arr [ i ] give a perfect square ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > getPerfectSquares ( int n ) { vector < int > perfectSquares ; int current = 1 , i = 1 ; while ( current <= n ) { perfectSquares . push_back ( current ) ; current = static_cast < int > ( pow ( ++ i , 2 ) ) ; } return perfectSquares ; } 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 ) ; } 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 ; if ( temp > n && find ( nums . begin ( ) , nums . end ( ) , temp ) != nums . end ( ) ) { count ++ ; } } return count ; } int countPairs ( vector < int > & arr ) { int i , n = arr . size ( ) ; int max = maxPairSum ( arr ) ; vector < int > perfectSquares = getPerfectSquares ( max ) ; unordered_set < int > nums ; for ( i = 0 ; i < n ; i ++ ) { nums . insert ( arr [ i ] ) ; } int count = 0 ; for ( i = 0 ; i < n ; i ++ ) { count += countPairsWith ( arr [ i ] , perfectSquares , nums ) ; } return count ; } int main ( ) { vector < int > arr = { 2 , 3 , 6 , 9 , 10 , 20 } ; cout << countPairs ( arr ) << endl ; return 0 ; }