By Dhanadeepa_Red, history, 12 months ago, ,

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.

•
• -12
•

 » 12 months ago, # |   +5 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).
•  » » 12 months ago, # ^ |   0 I did this.I am looking for better approach?
•  » » » 12 months ago, # ^ |   +19 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 indexI won't explain further, if you want to know more details solve FFT problems and maybe read this: http://codeforces.com/blog/entry/43499
•  » » 12 months ago, # ^ |   0 Can you further describe the two pointer approach @praran26? And I assume that the array must be sorted before using such an approach?
•  » » » 12 months ago, # ^ |   0 Yes, you will have to sort the array first. Check out this for two pointer approach.