Bit Manipulation - Maximum XOR of Two Numbers
What is the time complexity of the trie-based maximum XOR algorithm for an input array of size n, where each number fits in 32 bits?
What is the time complexity of the trie-based maximum XOR algorithm for an input array of size n, where each number fits in 32 bits?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Solution:
Step 1: Identify operations per number
Each number is inserted into the trie by processing 32 bits, so insertion is O(32) per number.Step 2: Find max XOR per number
For each number, traversing trie to find max XOR also takes O(32) steps.Final Answer:
Option D -> Option DQuick Check:
Overall complexity is O(n * 32) = O(n), since 32 is constant [OK]
Quick Trick: 32 bits fixed, so linear in n [OK]
Common Mistakes:
MISTAKES- Confusing log M with n
- Assuming quadratic due to nested loops
- Counting 32^2 instead of 32
Trap Explanation:
PITFALL- Option B looks right but log M = 32 is constant, so complexity is O(n * 32) not O(n * log M) as variable.
Interviewer Note:
CONTEXT- Checks if candidate understands bit-level complexity and constants in big-O.
Master "Maximum XOR of Two Numbers" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes