What is the time complexity of the XOR approach to find the missing number in an array of length n containing numbers from 0 to n with one missing?

medium🪤 Complexity Trap Q13 of Q15

Bit Manipulation - Find the Missing Number

AO(n log n) due to sorting inside XOR operations

BO(1) since XOR is a constant time operation

CO(n^2) because XOR operations are nested

DO(n) because it iterates over the range and array once each

Step-by-Step Solution

Step 1: Identify loops in the XOR approach
There are two separate loops: one over range 0 to n, and one over the array of length n.
Step 2: Calculate total time complexity
Each loop runs O(n) times, so total time is O(n) + O(n) = O(n).
Final Answer:
Option D -> Option D
Quick Check:
No nested loops or sorting, linear time confirmed [OK]

Quick Trick: Two separate linear loops sum to O(n) time [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

XOR looks like a constant time op but is done n times; candidates confuse nested vs sequential loops.

Interviewer Note:

CONTEXT

Checks if candidate understands iteration cost and does not confuse operation cost with loop cost

Master "Find the Missing Number" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Bit Manipulation Quizzes