Count all triplets whose sum is equal to a perfect cube | C ++ program to calculate all triplets whose sum is perfect cube . ; Function to calculate all occurrence of a number in a given range ; if i == 0 assign 1 to present state ; else add + 1 to current state with previous state ; Function to calculate triplets whose sum is equal to the perfect cube ; Initialize answer ; count all occurrence of third triplet in range from j + 1 to n ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 1001 ] [ 15001 ] ; void computeDpArray ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 1 ; j <= 15000 ; ++ j ) { if ( i == 0 ) dp [ i ] [ j ] = ( j == arr [ i ] ) ; else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + ( arr [ i ] == j ) ; } } } int countTripletSum ( int arr [ ] , int n ) { computeDpArray ( arr , n ) ; int ans = 0 ; for ( int i = 0 ; i < n - 2 ; ++ i ) { for ( int j = i + 1 ; j < n - 1 ; ++ j ) { for ( int k = 1 ; k <= 24 ; ++ k ) { int cube = k * k * k ; int rem = cube - ( arr [ i ] + arr [ j ] ) ; if ( rem > 0 ) ans += dp [ n - 1 ] [ rem ] - dp [ j ] [ rem ] ; } } } return ans ; } int main ( ) { int arr [ ] = { 2 , 5 , 1 , 20 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countTripletSum ( arr , n ) ; return 0 ; }