Kth Missing Positive Number
Easy About 10 min Free, no account needed
Find the k-th positive integer the sorted array skipped.
The brief
Given a strictly increasing array of positive integers arr and a positive
k, return the k-th positive integer missing from the array.
The obvious approach walks candidates 1, 2, 3, ... counting the misses. The hidden
test asks for the billionth missing number, so a linear walk is far too
slow. Note that before arr[i] exactly arr[i] - (i + 1) numbers are
missing, a quantity that only grows as i grows, which lets you locate the
answer in O(log n) rather than scanning.
Starter code
using System;
public class Solution
{
// TODO: return the k-th positive integer absent from the strictly increasing array.
public long KthMissing(int[] arr, long k)
{
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
- Binary search
- Halve a sorted search space, with exact boundaries and no off-by-one drift.
Related katas
- Batched Binary Search Easy Free Answer twenty thousand membership queries against a sorted array.
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.
- Minimum Travel Pass Cost Medium Free Cover sparse travel dates with overlapping pass durations while paying for no unnecessary calendar state.
- Weighted Reservation Schedule Hard Free Choose a maximum-value set of nonoverlapping reservations with a mandatory cleanup gap.