Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

What it practices

Binary search
Halve a sorted search space, with exact boundaries and no off-by-one drift.

Related katas