I have the following algorithm, can somebody help me solve this? I just need an explanation.

"A vector a[] with n integer elements is cube-repetition-free if no element is the cube of another element, i.e., there are no indices i,j such that a[i] = a[j]3 . Propose an O(n*log(n))-time algorithm in order to decide whether a vector is cube-repetition-free."

CodePudding user response：

O(n) solution:

1. Add each element v[i] of the vector to a hash set.
2. For each element v[i] check whether v[i] * v[i] * v[i] is in the set.

O(n*logn) solution:

1. Sort the vector v.
2. Pointers start = 0 and end = 1.
3. While end < n do the following:
   1. if v[start] * v[start] * v[start] equals v[end] then the vector is not cube-repetition-free.
   2. if v[start] * v[start] * v[start] < v[end] then increment start.
   3. Otherwise increment end.