268. Missing Number

🟩 Easy

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 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2

Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3

Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints

• n == nums.length

• 1 <= n <= 10^4

• 0 <= nums[i] <= n

• All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

My Solution (Gauss Formula)

func missingNumber(nums []int) int {
    n := len(nums)

    sum := n*(n+1)/2

    for _, num := range nums {
        sum -= num
    }

    return sum
}

Optimal Solution 1 (XOR)

func missingNumber(nums []int) int {
    result := len(nums)
    
    // XOR all numbers from 0 to n with array elements
    for i := 0; i < len(nums); i++ {
        result ^= i ^ nums[i]
    }
    
    return result
}

Optimal Solution 2 (Cyclic Sort)

func missingNumber(nums []int) int {
    i := 0
    n := len(nums)
    
    // Place each number in its correct position
    for i < n {
        pos := nums[i]
        if pos < n && pos != i {
            nums[i], nums[pos] = nums[pos], nums[i]
        } else {
            i++
        }
    }
    
    // Find the missing number
    for i := 0; i < n; i++ {
        if nums[i] != i {
            return i
        }
    }
    
    return n
}

Approach Analysis

This problem showcases different mathematical and algorithmic approaches:

1. Gauss Formula (Your Solution):

   • Use mathematical formula for sum

   • Subtract array elements

   • Simple and elegant

   • No modification to input

2. XOR Approach:

   • Use XOR properties

   • Cancellation of pairs

   • Constant extra space

   • Bit manipulation technique

3. Cyclic Sort:

   • Place numbers in position

   • In-place modification

   • Index-based approach

   • Useful for similar problems

Visualization of Approaches

Gauss Formula Process (Your Solution)

Input: [3,0,1]
n = 3

Step 1: Expected sum = n*(n+1)/2
                    = 3*(3+1)/2
                    = 3*4/2
                    = 6

Step 2: Actual sum = 3 + 0 + 1 = 4

Step 3: Missing = Expected - Actual
                = 6 - 4
                = 2

XOR Process

Input: [3,0,1]
n = 3

Step 1: result = 3 (length)
Step 2: result = 3 ^ 0 ^ 3
Step 3: result = 3 ^ 1 ^ 0
Step 4: result = 3 ^ 2 ^ 1
Final: result = 2

Cyclic Sort Process

Input: [3,0,1]

Step 1: [3,0,1] → swap 3 and 1 → [1,0,3]
Step 2: [1,0,3] → swap 1 and 0 → [0,1,3]
Step 3: [0,1,3] → array sorted

Check indices:
index 0: nums[0] = 0 
index 1: nums[1] = 1 
index 2: nums[2] = 3 
Missing: 2

Complexity Analysis

Gauss Formula (Your Solution)

• Time: O(n)

  • Single pass through array

  • Simple arithmetic

  • No sorting required

• Space: O(1)

  • Only use sum variable

  • Constant extra space

  • No additional storage

XOR Solution

• Time: O(n)

  • Single pass through array

  • Constant time operations

  • Bit manipulation

• Space: O(1)

  • Only use result variable

  • In-place operations

  • Most space efficient

Cyclic Sort Solution

• Time: O(n)

  • Two passes through array

  • Each element moved once

  • Index-based checking

• Space: O(1)

  • In-place sorting

  • No extra storage

  • Modifies input array

Why Solutions Work

1. Gauss Formula:

   • Sum formula is exact

   • Difference shows missing

   • Works for any range

   • Mathematical proof

2. XOR Properties:

   • a^a = 0

   • a^0 = a

   • XOR is associative

   • Missing number remains

3. Cyclic Sort:

   • Numbers match indices

   • Missing creates gap

   • Natural ordering

   • Index-value relationship

When to Use

1. Gauss Formula When:

   • Can't modify input

   • Simple solution needed

   • Mathematical approach ok

   • Range is consecutive

2. XOR When:

   • Memory is critical

   • Bit operations allowed

   • No overflow concern

   • Performance critical

3. Cyclic Sort When:

   • Can modify array

   • Need sorted result

   • Similar problems follow

   • Index-based problems

Common Patterns & Applications

1. Related Problems:

   • Find All Numbers Disappeared

   • Single Number

   • First Missing Positive

   • Find the Duplicate Number

2. Key Techniques:

   • Mathematical formulas

   • Bit manipulation

   • In-place sorting

   • Index as hash key

Interview Tips

1. Solution Highlights:

   • Multiple approaches

   • Space-time tradeoffs

   • Bit manipulation

   • Mathematical insight

2. Common Pitfalls:

   • Integer overflow

   • Edge cases (0, n)

   • Modifying input

   • Off-by-one errors

3. Testing Strategy:

   • Missing first number

   • Missing last number

   • Single element array

   • Maximum size array

   • Sequential numbers

4. Follow-up Questions:

   • Multiple missing numbers?

   • Negative numbers?

   • Stream of numbers?

   • Memory constraints?

result

Leetcode: link