Missing Number
Easy About 8 min Free, no account needed
Which value from 0..n is absent? Arithmetic answers in one pass.
The brief
nums contains n distinct values from the range 0..n, exactly one
value of the range is missing. Return it.
The obvious approach tries each candidate 0, 1, 2, ... and scans the array for it,
O(n2) when the missing value is large. The hidden test misses 199,999,
so the quadratic scan is too slow. You will need an approach that runs in a single
pass, O(n).
Starter code
using System;
public class Solution
{
// TODO: return the one value of 0..n absent from nums.
public int MissingNumber(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Add Binary Strings Easy Free Add two binary numbers far too long for any built-in integer.
- Base64 Decoded Length Easy Free The decoded size is pure arithmetic - no need to decode.
- Count Missing Sample Runs Easy Free Count every contiguous interval with no recorded sample, even when the timeline is too large to expand.
- Excel Column Number Easy Free Spreadsheet columns are base-26 with no zero digit.