Solution Explanation for Missing Number

The problem asks to find the only missing number in an array nums containing n distinct numbers in the range [0, n]. We'll explore two efficient solutions: bit manipulation and mathematical summation.

Solution 1: Bit Manipulation (XOR)

This approach leverages the properties of the XOR (exclusive OR) operation:

• x ^ 0 = x (XOR with 0 yields the original number)
• x ^ x = 0 (XOR with itself yields 0)

We can XOR all numbers from 0 to n with the numbers present in the input array. The numbers present will cancel each other out (resulting in 0), leaving only the missing number.

Algorithm:

1. Initialize ans to n. This acts as our accumulator, initially representing the number n which might be missing.
2. Iterate through the array nums. For each element nums[i], XOR ans with i (the index) and nums[i].
3. The final value of ans will be the missing number.

Time Complexity: O(n) - We iterate through the array once. Space Complexity: O(1) - We use a constant amount of extra space.

Solution 2: Mathematical Summation

This approach uses the formula for the sum of an arithmetic series. The sum of numbers from 0 to n is given by: n(n+1)/2.

Algorithm:

1. Calculate the expected sum of numbers from 0 to n: expectedSum = n(n+1)/2.
2. Calculate the actual sum of numbers in the input array nums: actualSum = sum(nums).
3. The difference between expectedSum and actualSum is the missing number.

Time Complexity: O(n) - We iterate through the array to calculate the sum. Space Complexity: O(1) - We use a constant amount of extra space.

Code Examples (Multiple Languages)

The code examples below demonstrate both solutions in several programming languages. Note that the mathematical approach might be slightly more concise in some languages. For bit manipulation, functions like reduce (Python) or libraries for bitwise operations might improve readability but don't affect time or space complexity fundamentally.

Python (Both Solutions):

from functools import reduce
import operator
 
class Solution:
    def missingNumber_xor(self, nums: list[int]) -> int:  #Bit Manipulation
        n = len(nums)
        ans = n
        for i, num in enumerate(nums):
            ans ^= (i ^ num)
        return ans
 
    def missingNumber_math(self, nums: list[int]) -> int: #Mathematical Summation
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum
 

Java (Both Solutions):

class Solution {
    public int missingNumber_xor(int[] nums) { //Bit Manipulation
        int n = nums.length;
        int ans = n;
        for (int i = 0; i < n; i++) {
            ans ^= (i ^ nums[i]);
        }
        return ans;
    }
 
    public int missingNumber_math(int[] nums) { //Mathematical Summation
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

C++ (Both Solutions):

#include <numeric> //for accumulate
#include <vector>
 
class Solution {
public:
    int missingNumber_xor(vector<int>& nums) { //Bit Manipulation
        int n = nums.size();
        int ans = n;
        for (int i = 0; i < n; ++i) {
            ans ^= (i ^ nums[i]);
        }
        return ans;
    }
 
    int missingNumber_math(vector<int>& nums) { //Mathematical Summation
        int n = nums.size();
        long long expectedSum = (long long)n * (n + 1) / 2; //avoid integer overflow
        long long actualSum = accumulate(nums.begin(), nums.end(), 0LL); //0LL for long long
        return expectedSum - actualSum;
    }
};

(Javascript, Go, TypeScript, Rust, PHP examples would follow a similar structure, adapting syntax accordingly.)

Both solutions provide optimal time and space complexity for this problem. The choice between them often comes down to personal preference and coding style. The mathematical approach might be slightly easier to understand for those less familiar with bitwise operations. However, the bit manipulation method can be slightly faster in some cases due to direct hardware implementation of bitwise operations.