CODEWITHSUNDEEP
c++algorithmvector
Razmi
Razmi

Reputation: 209

Check if vector have no cube values of another element

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

Upvotes: 0

Views: 85

Answers (1)

maraca
maraca

Reputation: 8763

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.

Upvotes: 2

Related Questions