Missing Number - Practice Coding Problems

Missing Number - Problem

Array Hash Table Math Binary Search Bit Manipulation Sorting 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.

Note: The array contains exactly n numbers, where each number is unique and falls within the range [0, n]. Your task is to find the single missing number.

Input & Output

Example 1 — Basic Missing Number

$ Input: nums = [3,0,1]

› Output: 2

💡 Note: Array has numbers [3,0,1] from range [0,3]. The missing number is 2.

Example 2 — Missing First Number

$ Input: nums = [0,1]

› Output: 2

💡 Note: Array has numbers [0,1] from range [0,2]. The missing number is 2.

Example 3 — Missing Zero

$ Input: nums = [9,6,4,2,3,5,7,0,1]

› Output: 8

💡 Note: Array has 9 numbers from range [0,9]. After checking, 8 is missing.

Constraints

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
All numbers in nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array with n distinct numbers from range [0,n]

Process

Find which number from 0 to n is not present

Output

Return the missing number

Key Takeaway

🎯 Key Insight: Use mathematical sum formula or XOR properties to find missing number in O(n) time and O(1) space

Asked in

M Microsoft 45 a Amazon 38 G Google 32 🍎 Apple 28

The key insight is that we can find the missing number using mathematical properties or bit manipulation. The optimal approaches are the mathematical sum (expected sum - actual sum) and XOR bit manipulation, both achieving O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ XOR Bit Manipulation	O(n)	O(1)	Use XOR properties: a^a=0, a^0=a to cancel out pairs
Mathematical Sum	O(n)	O(1)	Use sum formula: expected sum minus actual sum equals missing number
Hash Set Approach	O(n)	O(n)	Use hash set to store numbers, then check which is missing
Brute Force	O(n²)	O(1)	For each number 0 to n, check if it exists in array

XOR Bit Manipulation — Algorithm Steps

Initialize result with 0
XOR result with all numbers from 0 to n
XOR result with all array elements
Remaining value is the missing number

Visualization

Tap to expand

Step-by-Step Walkthrough

XOR Range

XOR all numbers 0 to n

XOR Array

XOR with all array elements

Result

Matching numbers cancel, missing remains

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int size) {
    int result = 0;
    // XOR with all numbers from 0 to n
    for (int i = 0; i <= size; i++) {
        result ^= i;
    }
    // XOR with all array elements
    for (int i = 0; i < size; i++) {
        result ^= nums[i];
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int nums[100];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array and range 0 to n

✓ Linear Growth

Space Complexity

O(1)

Only using one variable to store XOR result

✓ Linear Space

307.6K Views

High Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

XOR Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler