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://mirror.codeforces.com/blog/entry/43499
Can you further describe the two pointer approach @TooDumbToWin? 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.