force_awakens's blog

Maximum XOR subsequence
By force_awakens, history, 7 years ago, In English

We can solve the maximum (AND) subsequence of an array by checking the common bits in numbers in O(nlogn).But how can we find a susequence with maximum XOR?

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

Comments Comments (1)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

One thing about maximum AND subsequence:

When you do AND operation with 2 numbers, then it is always true that result ≤ min(firstnum, secondnum). Can be proved easily. So, maximum AND subsequence in array is maximum number in array.

→ Reply