Skip to main content
DevHives

K-th Missing Positive Number

EasyArraysBinary search243 tests

You get an array arr of positive integers in strictly increasing order, and an integer k.

Count the positive integers 1, 2, 3, ... and skip every number that is in arr. Return the k-th number that you did not skip.

Note

The answer can be larger than every value in arr.

Hint: before index i, exactly arr[i] - (i + 1) positive numbers are missing. This count never goes down as i grows, so you can binary search on it.

Examples

Example 1

Input:
[3,4,8,10], 4
Output:
6

The missing numbers are 1, 2, 5, 6, 7, 9, 11, ... The 4th of them is 6.

Example 2

Input:
[1,2,3], 2
Output:
5

Nothing is missing up to 3. After that the missing numbers are 4, 5, 6, ... The 2nd is 5.

Example 3

Input:
[6,9], 3
Output:
3

The numbers 1 to 5 are all missing, so the 3rd missing number is 3.

Constraints

  • 1 <= arr.length <= 30
  • 1 <= arr[i] <= 300
  • arr[i] < arr[i + 1]
  • 1 <= k <= 300

Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.