algoadvance

Leetcode 268. Missing Number

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Clarifying Questions

  1. Input Constraints: Can the input array be empty?
    • No, the input array has at least one number. It contains numbers in the range [0, n] inclusive, where n is the length of the array.
  2. Uniqueness: Are all numbers in the input array unique?
    • Yes, all numbers in the array are distinct.
  3. Range: Is there any guarantee about the range of numbers in the array?
    • Yes, the numbers are guaranteed to be in the interval [0, n].

Strategy

  1. Sum Formula Approach:
    • The sum of the first n natural numbers is given by the formula ( \text{Sum} = \frac{n \times (n + 1)}{2} ).
    • Compute the sum of numbers in the input array.
    • The missing number will be the difference between the expected sum and the actual sum computed from the array.
  2. Bit Manipulation Approach:
    • Using XOR operation, we can effectively cancel out the numbers that appear in the array with the numbers from the complete range [0, n].
    • XOR all indices and all numbers in the array. The missing number will be the result.

Time Complexity

Code: Sum Formula Approach

#include <vector>

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

Code: Bit Manipulation Approach

#include <vector>

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int n = nums.size();
        int xor_sum = 0;
        
        // XOR all indices and all values in the array
        for (int i = 0; i <= n; ++i) {
            xor_sum ^= i;
        }
        for (int num : nums) {
            xor_sum ^= num;
        }
        
        return xor_sum;
    }
};

Conclusion

Both approaches are efficient with ( O(n) ) time complexity and ( O(1) ) space complexity. The sum formula approach is more intuitive, while the bit manipulation approach may be considered more elegant by some due to the clever use of XOR properties. Both solutions will accurately solve the problem as per the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI