# Count all triplets whose sum is equal to a perfect cube

Given an array of n integers, count all different triplets whose sum is equal to the perfect cube i.e, for any i, j, k(i < j < k) satisfying the condition that a[i] + a[j] + a[j] = X3 where X is any integer. 3 ≤ n ≤ 1000, 1 ≤ a[i, j, k] ≤ 5000
Example:

```Input:
N = 5
2 5 1 20 6
Output:
3
Explanation:
There are only 3 triplets whose total sum is a perfect cube.
Indices  Values SUM
0 1 2    2 5 1   8
0 1 3    2 5 20  27
2 3 4    1 20 6  27
Since 8 and 27 are prefect cube of 2 and 3.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive appraoch
is to iterate over all the possible numbers by using 3 nested loops and check whether their sum is a perfect cube or not. The approach would be very slow as time complexity can go up to O(n3).

An Efficient approach is to use dynamic programming and basic mathematics. According to the given condition sum of any of three positive integers is not greater than 15000. Therefore there can be only 24(150001/3) cubes are possible in the range of 1 to 15000.
Now instead of iterating all triplets we can do much better by the help of above information. Fixed first two indices i and j such that instead of iterating over all k(j < k ≤ n), we can iterate over all the 24 possible cubes, and for each one, (let's say P) check how many occurrence of P – (a[i] + a[j]) are in a[j+1, j+2, … n].
But if we compute the number of occurrences of a number say K in a[j+1, j+2, … n] then this would again be counted as slow approach and would definitely give TLE. So we have to think of a different approach.
Now here comes to a Dynamic Programming. Since all numbers are smaller than 5000 and n is at most 1000. Hence we can compute a DP array as,
dp[i][K]:= Number of occurance of K in A[i, i+1, i+2 … n]

## C++

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

## Java

 `// JAVA Code for Count all triplets whose ` `// sum is equal to a perfect cube ` `import` `java.util.*; ` ` `  `class` `GFG { ` `     `  `    ``public` `static` `int` `dp[][]; ` `     `  `    ``// Function to calculate all occurrence of ` `    ``// a number in a given range ` `    ``public` `static` `void` `computeDpArray(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < n; ++i) { ` `            ``for` `(``int` `j = ``1``; j <= ``15000``; ++j) { ` `      `  `                ``// if i == 0 ` `                ``// assign 1 to present state ` `                 `  `                ``if` `(i == ``0` `&& j == arr[i]) ` `                    ``dp[i][j] = ``1``; ` `                ``else` `if``(i==``0``) ` `                     ``dp[i][j] = ``0``; ` ` `  `                ``// else add +1 to current state  ` `                ``// with previous state ` `                ``else` `if``(arr[i] == j) ` `                    ``dp[i][j] = dp[i - ``1``][j] + ``1``; ` `                ``else` `                    ``dp[i][j] = dp[i - ``1``][j]; ` `            ``} ` `        ``} ` `    ``} ` `      `  `    ``// Function to calculate triplets whose sum ` `    ``// is equal to the pefect cube ` `    ``public` `static` `int` `countTripletSum(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``computeDpArray(arr, n); ` `         `  `        ``int` `ans = ``0``;  ``// Initialize answer ` `        ``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]); ` `      `  `                    ``// count all occurrence of  ` `                    ``// third triplet in range  ` `                    ``// from j+1 to n ` `                    ``if` `(rem > ``0``) ` `                        ``ans += dp[n - ``1``][rem] - dp[j][rem]; ` `                ``} ` `            ``} ` `        ``} ` `        ``return` `ans; ` `    ``} ` `     `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `arr[] = { ``2``, ``5``, ``1``, ``20``, ``6` `}; ` `        ``int` `n = arr.length; ` `        ``dp = ``new` `int``[``1001``][``15001``]; ` `         `  `        ``System.out.println(countTripletSum(arr, n)); ` `       `  `    ``} ` `} ` `     `  `// This code is contributed by Arnav Kr. Mandal.     `

## Python3

 `# Python 3 program to calculate all  ` `# triplets whose sum is perfect cube. ` ` `  `dp ``=` `[[``0` `for` `i ``in` `range``(``15001``)]  ` `         ``for` `j ``in` `range``(``1001``)] ` ` `  `# Function to calculate all occurrence  ` `# of a number in a given range ` `def` `computeDpArray(arr, n): ` `    ``for` `i ``in` `range``(n): ` `        ``for` `j ``in` `range``(``1``, ``15001``, ``1``): ` `             `  `            ``# if i == 0 ` `            ``# assign 1 to present state ` `            ``if` `(i ``=``=` `0``): ` `                ``dp[i][j] ``=` `(j ``=``=` `arr[i]) ` ` `  `            ``# else add +1 to current state with ` `            ``# previous state ` `            ``else``: ` `                ``dp[i][j] ``=` `dp[i ``-` `1``][j] ``+` `(arr[i] ``=``=` `j) ` `     `  `# Function to calculate triplets whose  ` `# sum is equal to the pefect cube ` `def` `countTripletSum(arr, n): ` `    ``computeDpArray(arr, n) ` `     `  `    ``ans ``=` `0` `# Initialize answer ` `    ``for` `i ``in` `range``(``0``, n ``-` `2``, ``1``): ` `        ``for` `j ``in` `range``(i ``+` `1``, n ``-` `1``, ``1``): ` `            ``for` `k ``in` `range``(``1``, ``25``, ``1``): ` `                ``cube ``=` `k ``*` `k ``*` `k ` ` `  `                ``rem ``=` `cube ``-` `(arr[i] ``+` `arr[j]) ` ` `  `                ``# count all occurrence of third  ` `                ``# triplet in range from j+1 to n ` `                ``if` `(rem > ``0``): ` `                    ``ans ``+``=` `dp[n ``-` `1``][rem] ``-` `dp[j][rem] ` `     `  `    ``return` `ans ` ` `  `# Driver code ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``arr ``=` `[``2``, ``5``, ``1``, ``20``, ``6``] ` `    ``n ``=` `len``(arr) ` `    ``print``(countTripletSum(arr, n)) ` ` `  `# This code is contributed by ` `# Sahil_Shelangia `

## C#

 `// C# Code for Count all triplets whose ` `// sum is equal to a perfect cube ` `using` `System; ` ` `  `class` `GFG  ` `{ ` ` `  `public` `static` `int` `[,]dp; ` ` `  `// Function to calculate all occurrence  ` `// of a number in a given range ` `public` `static` `void` `computeDpArray(``int` `[]arr,  ` `                                  ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i < n; ++i)  ` `    ``{ ` `        ``for` `(``int` `j = 1; j <= 15000; ++j)  ` `        ``{ ` ` `  `            ``// if i == 0 ` `            ``// assign 1 to present state ` `             `  `            ``if` `(i == 0 && j == arr[i]) ` `                ``dp[i, j] = 1; ` `            ``else` `if``(i == 0) ` `                ``dp[i, j] = 0; ` ` `  `            ``// else add +1 to current state  ` `            ``// with previous state ` `            ``else` `if``(arr[i] == j) ` `                ``dp[i, j] = dp[i - 1, j] + 1; ` `            ``else` `                ``dp[i, j] = dp[i - 1, j]; ` `        ``} ` `    ``} ` `} ` ` `  `// Function to calculate triplets whose  ` `// sum is equal to the pefect cube ` `public` `static` `int` `countTripletSum(``int` `[]arr,  ` `                                  ``int` `n) ` `{ ` `    ``computeDpArray(arr, n); ` `     `  `    ``int` `ans = 0; ``// Initialize answer ` `    ``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]); ` ` `  `                ``// count all occurrence of  ` `                ``// third triplet in range  ` `                ``// from j+1 to n ` `                ``if` `(rem > 0) ` `                    ``ans += dp[n - 1, rem] -  ` `                           ``dp[j, rem]; ` `            ``} ` `        ``} ` `    ``} ` `    ``return` `ans; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `Main()  ` `{ ` `    ``int` `[]arr = { 2, 5, 1, 20, 6 }; ` `    ``int` `n = arr.Length; ` `    ``dp = ``new` `int``[1001, 15001]; ` `     `  `    ``Console.Write(countTripletSum(arr, n)); ` `} ` `} ` ` `  `// This code is contributed ` `// by 29AjayKumar `

## PHP

 ` 0) ` `                    ``\$ans` `+= ``\$dp``[``\$n` `- 1][``\$rem``] -  ` `                            ``\$dp``[``\$j``][``\$rem``]; ` `            ``} ` `        ``} ` `    ``} ` `    ``return` `\$ans``; ` `} ` ` `  `// Driver code ` `\$arr` `= ``array``(2, 5, 1, 20, 6); ` `\$n` `= sizeof(``\$arr``); ` `echo` `countTripletSum(``\$arr``, ``\$n``); ` ` `  `// This code is contributed by ita_c ` `?> `

Output:

``` 3
```

Time complexity: O(N2*24)
Auxiliary space: O(107)