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.

Example 1:

• Input: nums = [3,0,1]
• Output: 2

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n

Sum formula n * (n + 1) / 2 minus array sum gives missing number.

Gauss Sum / Bitwise XOR

graph TD
    A["Input Integer / Bits"] --> B["Apply Bitwise Operation (AND / XOR / Shift)"]
    B --> C{"Check Bit Condition"}
    C -- "Condition Met" --> D["Update Bit Count / Result"]
    C -- "Continue" --> E["Shift Bits (>>> 1 or & n-1)"]
    E --> B
    D --> F["Return Final Result"]

function missingNumber(nums) {
  const n = nums.length;
  let expected = (n * (n + 1)) / 2;
  let actual = nums.reduce((a, b) => a + b, 0);
  return expected - actual;
}

• Time Complexity: O(n)
• Space Complexity: O(1)
• Explanation: Gauss sum.

function missingNumber(nums) {
  const n = nums.length;
  let expected = (n * (n + 1)) / 2;
  let actual = nums.reduce((a, b) => a + b, 0);
  return expected - actual;
}

• Time Complexity: O(n)
• Space Complexity: O(1)
• Explanation: Gauss summation formula.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

Subtract total array sum from total expected sum n*(n+1)/2.

1. Sum from 0 to n is n * (n + 1) / 2.

👉 Solve this problem interactively in the DSA Lab