Count of pairs in an array whose sum is a perfect square | 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
def getPerfectSquares ( n ) : NEW_LINE INDENT perfectSquares = [ ] ; NEW_LINE current = 1 ; NEW_LINE i = 1 ; NEW_LINE while ( current <= n ) : NEW_LINE INDENT perfectSquares . append ( current ) ; NEW_LINE i += 1 ; NEW_LINE current = int ( pow ( i , 2 ) ) ; NEW_LINE DEDENT return perfectSquares ; NEW_LINE DEDENT def maxPairSum ( arr ) : NEW_LINE INDENT n = len ( arr ) ; NEW_LINE max = 0 ; NEW_LINE secondMax = 0 ; NEW_LINE if ( arr [ 0 ] > arr [ 1 ] ) : NEW_LINE INDENT max = arr [ 0 ] ; NEW_LINE secondMax = arr [ 1 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT max = arr [ 1 ] ; NEW_LINE secondMax = arr [ 0 ] ; NEW_LINE DEDENT for i in range ( 2 , n ) : NEW_LINE INDENT if ( arr [ i ] > max ) : NEW_LINE INDENT secondMax = max ; NEW_LINE max = arr [ i ] ; NEW_LINE DEDENT elif ( arr [ i ] > secondMax ) : NEW_LINE INDENT secondMax = arr [ i ] ; NEW_LINE DEDENT DEDENT return ( max + secondMax ) ; NEW_LINE DEDENT def countPairsWith ( n , perfectSquares , nums ) : NEW_LINE INDENT count = 0 ; NEW_LINE for i in range ( len ( perfectSquares ) ) : NEW_LINE INDENT temp = perfectSquares [ i ] - n ; NEW_LINE if ( temp > n and ( temp in nums ) ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT DEDENT return count ; NEW_LINE DEDENT def countPairs ( arr ) : NEW_LINE INDENT n = len ( arr ) ; NEW_LINE max = maxPairSum ( arr ) ; NEW_LINE perfectSquares = getPerfectSquares ( max ) ; NEW_LINE nums = [ ] ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT nums . append ( arr [ i ] ) ; NEW_LINE DEDENT count = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT count += countPairsWith ( arr [ i ] , perfectSquares , nums ) ; NEW_LINE DEDENT return count ; NEW_LINE DEDENT arr = [ 2 , 3 , 6 , 9 , 10 , 20 ] ; NEW_LINE print ( countPairs ( arr ) ) ; NEW_LINE