268. Missing Number

📝 Problem Details

• Title: 268. Missing Number
• Link: https://leetcode.com/problems/missing-number/
• Difficulty: Easy
• Tags/Categories: Bit-Manipulation

Already Solved ⇒ 268. Missing Number

Note: Solved without the use of bit manipulation

Bit Manipulation Approach:

We can leverage the properties of XOR:

🔸 Property:
  - a ^ a = 0
  - a ^ 0 = a
  - XOR is associative and commutative

🔸 Idea:
  - XOR all indices from 0 to n, and XOR all values in the array.
  - Since all numbers in the array are present except one, all duplicates will cancel out.
  - What’s left is the missing number.

🔸 Example:
  nums = [3, 0, 1]
  n = 3
  XOR(0 ^ 1 ^ 2 ^ 3) ^ XOR(3 ^ 0 ^ 1) = 2 (missing)

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Implementation

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int missing = nums.size();
        for(int i=0; i < nums.size(); i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
};