wish_me's blog

Count all triplets whose sum is equal to a perfect cube
By wish_me, history, 7 years ago, In English

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.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did this.I am looking for better approach?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      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

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply