268. Missing Number.md

268. Missing Number | C++ Solution | Optimized Approach | XOR, Sum & Sort-Search

Intuition

The problem is asking to find the missing number in an array that contains n distinct numbers taken from 0, 1, 2, ..., n. This means that one number is missing and we need to find it.

Approach

1. XOR: The XOR of a number with itself is 0. If we take the XOR of all the indiceRRs and the numbers in the array, we will be left with the missing number.

2. Sum: The sum of the first n natural numbers is n*(n+1)/2. If we subtract the sum of the numbers in the array from this, we will get the missing number.

3. Sort & Search: If we sort the array, the missing number will be the first number such that the difference between it and the next number is more than 1, or that number would be the first number which is not equal to its indices.

Complexity

• XOR

  • Time complexity: $O(n)$
  • Space complexity: $O(1)$

• Sum

  • Time complexity: $O(n)$
  • Space complexity: $O(1)$

• Sort & Search

  • Time complexity: $O(n \log n)$
  • Space complexity: $O(1)$

Code

1. XOR :

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

        return ans;
    }
};

2. Sum :

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        for (int num : nums) {
            total -= num;
        }

        return total;
    }
};

3. Sort & Search :

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        return nums.size();
    }
};