Maximum XOR of Two Numbers in an Array
Radio towers share a list of channel codes. Two towers with codes a and b interfere by a XOR b, and a tower paired with itself gives 0. Return the largest interference over any pair of towers in the list. Codes may repeat, and a list with one tower answers 0. Limits: 1 <= codes.length <= 200000, each code from 0 to 2147483647. Every answer also fits in a 32-bit int. Think about: which bit of the answer can you settle first? Example: codes = [9, 4, 12, 3] => 15 9 = 1001, 4 = 0100, 12 = 1100, 3 = 0011 9 XOR 4 = 13, 9 XOR 12 = 5, 9 XOR 3 = 10 4 XOR 12 = 8, 4 XOR 3 = 7, 12 XOR 3 = 1111 = 15 The best pair is 12 and 3.
You get a list of numbers and want the largest XOR you can make from any two of them. Checking every pair is easy to write and quietly too slow, which is why interviewers ask: they want to see you treat numbers as strings of bits and settle the answer one bit at a time. The classic trap is hunting for the two biggest numbers when the best pair is often a mismatch. Expect up to 200,000 numbers, each from 0 to 2,147,483,647.
Examples
You write
find_maximum_xor(codes: List[int])
Example 1
- Input
- codes = [9,4,12,3]
- returns
- 15
Example 2
- Input
- codes = [7]
- returns
- 0
Save this for your laptop
The editor and Run need a bigger screen. The link opens Maximum XOR of Two Numbers in an Array ready to code. It is free, and the editor needs no account.
The pattern behind it
Bit Manipulation
I reach for it when
- The statement bans extra space or restricts operators.
- Numbers act as flags, masks or XOR pairs.
Say this before you type. Say what each bit means in this problem before you shift or mask anything.
All 12 Bit Manipulation problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.