codolove's blog

Finding sub-array with maximum xor
By codolove, 9 years ago, In English

I am trying to solve this question from many days but getting wrong answe always. I am using a trie to solve this. My code is here.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you are trying to solve the same problem that are solving here. Check it out, maybe you find the answer there. I couldn't see your code due to technical problems but I solve similar problems using tries too, so I think you are probably on the right way.

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

    I am again getting wrong answer on same type of problem here. I have checked on most of the inputs and it's giving correct answer. My solution is here. please do check this.

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

      Hi, you are considering only the first maximum value that appears, but you can get the same maximum value, with a lexicographic smallest subsequence. Try with this input:

      4
1 1 2 1

      Your output:

      3
2 3

      Correct output:

      3
1 4
      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'll give you a hint, write the maximum number in binary, it's going to have at most 20 digits, now it's obvious that you can have only one of each digit in the answer, and having a digit i is better than having digits 1 . . . i-1 since 2^i > 1 + 2 + . . . + 2^(i-1), so now each time try saving the digit with the most value and your done!

→ Reply