← DiffPush

Kth missing number

Baseline Binary Search · In Search Space O(log n) · O(1)

The k-th Silent Slot in an ID Sequence

A ticketing system allocates strictly increasing IDs, but outages left gaps in the issued sequence. Auditors reference issues by counting gaps - the k-th positive integer that was never issued. Find that value from the sorted list of issued IDs without walking every integer.

Input: An array arr of n strictly increasing positive integers and an integer k.

Output: The k-th positive integer missing from arr.

Constraints

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr is sorted in strictly increasing order

Examples

Example 1

Input: {"arr":[2,3,4,7,11],"k":5}
Output: 9
The missing IDs are 1, 5, 6, 8, 9 in order, so the fifth gap is 9.

Example 2

Input: {"arr":[1,2,3,4],"k":2}
Output: 6
Nothing is missing inside the range, so the gaps continue past the last ID: 5 then 6.

Solve this in your browser →

Also on LeetCode ↗