The problem
Return the largest value of nums[i] ^ nums[j] for two different positions i and j. ^ is XOR: a result bit is 1 where the two numbers’ bits differ.
max_xor([3, 10, 5, 25, 2, 8]) # 28, from 5 ^ 25
max_xor([1, 2]) # 3
max_xor([7, 7, 7]) # 0
In binary, 5 is 00101 and 25 is 11001, so 5 ^ 25 is 11100, which is 16 + 8 + 4 = 28.
Limits
- 2 to 20,000 numbers, each from 0 to 230 − 1 (at most 30 bits). Comparing every pair is too slow; aim for O(n · B) with B bits.
Builds on TRIE-5 Bitwise tries for XOR.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
9 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Six numbers | Not run | |
| 2 | The lesson's numbers | Not run | |
| 3 | Two numbers | Not run | |
| 4 | All the same | Not run | |
| 5 | Zeros | Not run | |
| 6 | Large values | Not run | |
| 7 | Powers of two | Not run | |
| 8 | The opposite bit is missing | Not run | |
| 9 | 20,000 numbers | Not run |