🧩 Missing Number — LeetCode Problem #268

📄 Problem Description

You are given an array nums containing n distinct numbers taken from the range [0, n].
Since one number in this range is missing, your task is to find that missing number.

Example:

Input: nums = [3, 0, 1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 
2 is the missing number.

---

💡 Approach — XOR Bit Manipulation

This solution uses the XOR (^) operator to find the missing number efficiently in O(n) time and O(1) extra space.

🧠 Logic Explanation

1. Start with xor = nums.length, since indices go from 0 to n-1 but the range includes n.
2. For each index i and corresponding number nums[i], XOR them with xor.
3. Due to XOR properties:
   • a ^ a = 0 (same numbers cancel out)
   • a ^ 0 = a
   • XOR is commutative and associative
4. Therefore, after XORing all indices and elements, only the missing number remains.

---

🔍 Dry Run Example

Input: nums = [3, 0, 1]
n = 3

Step	i	nums[i]	xor before	Operation	xor after
Init	-	-	3	-	3
1	0	3	3	3 ^ 0 ^ 3	0
2	1	0	0	0 ^ 1 ^ 0	1
3	2	1	1	1 ^ 2 ^ 1	2

✅ Final result: 2

---

🧾 Code

class Solution {
    public int missingNumber(int[] nums) {
        int xor = nums.length;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i ^ nums[i];
        }
        return xor;
    }
}

---

⚙️ Complexity Analysis

• Time Complexity: O(n)
  → One pass through the array.
• Space Complexity: O(1)
  → Uses only a single integer variable.

---

🏁 Summary

Method	Time	Space	Notes
XOR	O(n)	O(1)	Efficient and elegant bit manipulation approach

---

📚 Related Topics

• Bit Manipulation
• Array
• Math