Count of pairs in an Array whose sum is a Perfect Cube | C ++ implementation of the approach ; Function to return an ArrayList containing all the perfect cubes upto n ; while current perfect cube 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 cube ; 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 cube ; Sum of the maximum two elements from the array ; List of perfect cubes upto max ; Contains all the array elements ; Add count of the elements that when added with arr [ i ] give a perfect cube ; Driver code
#include <bits/stdc++.h> NEW_LINE #include <vector> NEW_LINE using namespace std ; vector < int > getPerfectcubes ( int n ) { vector < int > perfectcubes ; int current = 1 ; int i = 1 ; while ( current <= n ) { perfectcubes . push_back ( current ) ; i += 1 ; current = int ( pow ( i , 3 ) ) ; } return perfectcubes ; } int maxPairSum ( int arr [ ] , int n ) { int max = 0 ; int secondMax = 0 ; 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 > perfectcubes , vector < int > nums ) { int count = 0 ; int len = perfectcubes . size ( ) ; for ( int i = 0 ; i < len ; i ++ ) { int temp = perfectcubes [ i ] - n ; if ( temp > n ) { for ( auto j = nums . begin ( ) ; j != nums . end ( ) ; j ++ ) { if ( ( * j ) == temp ) count += 1 ; } } } return count ; } int countPairs ( int arr [ ] , int n ) { int max = maxPairSum ( arr , n ) ; vector < int > perfectcubes = getPerfectcubes ( max ) ; vector < int > nums ; for ( int i = 0 ; i < n ; i ++ ) nums . push_back ( arr [ i ] ) ; int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { count += countPairsWith ( arr [ i ] , perfectcubes , nums ) ; } return count ; } int main ( ) { int arr [ ] = { 2 , 6 , 18 , 9 , 999 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << ( countPairs ( arr , n ) ) ; }