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

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.

The maximum possible value of

`a[i]+a[j]+a[k]`

can be 15000. There are 24 perfect cubes less than 15000. You can check if there exists`(i,j,k)`

for a given perfect cube in O(n*n) using two pointers. The overall complexity will be O(24*n*n).I did this.I am looking for better approach?

There's an O(m*logm) solution using FFT where m is the maximum sum. Let A be the polynomial where a[i] = frequency of i, the answer for each sum will be on the coeficients of something like:

A^3 — polynomial of choosing 3 of the same index — polynomial of choosing 2 of the same index

I won't explain further, if you want to know more details solve FFT problems and maybe read this: http://codeforces.com/blog/entry/43499

Can you further describe the two pointer approach @praran26? And I assume that the array must be sorted before using such an approach?

Yes, you will have to sort the array first. Check out this for two pointer approach.