{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Missing Number – Solution & Complexity

Interview solutions
/
Missing Number

Solution Walkthrough

  1. Step 1: Use the range guarantee

    • The numbers must be exactly the values from 0 to n, except one missing entry.
    • That guarantee gives a closed-form expectation we can compare against the actual array.

  2. Step 2: Brute-force membership checks

    • For every value from 0 through n, scan the array to see whether it exists.
    • This works, but the nested search costs O(n^2) time.
    def missing_number(nums):
    n = len(nums)
    for candidate in range(n + 1):
        if candidate not in nums:
            return candidate
    return -1

  3. Step 3: Compare expected and actual totals

    • The full range 0..n sums to n * (n + 1) / 2.
    • Since exactly one value is missing and nothing is duplicated, subtracting the actual array sum reveals that missing value immediately.

  4. Step 4: Compute the missing value in one pass

    • First compute the expected range sum.
    • Then subtract every number in the array and return the remainder.
    def missing_number(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)
    return expected - actual

  5. Step 5: Dry run / arithmetic trace

    Trace nums = [3, 0, 1].

    quantityvalue
    n3
    expected sum 0 + 1 + 2 + 36
    actual array sum 3 + 0 + 14
    missing number expected - actual2

    Because the array contains distinct numbers, no extra bookkeeping is needed beyond the running total.

  6. Step 6: Final solution and complexity

    The sum formula finds the missing value in O(n) time and O(1) extra space.

    def missing_number(nums: list[int]) -> int:
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)
    return expected - actual

FAQ

See also

Practice Missing Number online (run code in the browser)Pascal's Triangle solution (easy)Plus One solution (easy)Single Number solution (easy)Single Number II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?