Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example

Input: arr=[2,3,4,7,11], k=5

Output: 9

Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Python solution

def binary_search(arr: List[int], k: int) -> int: if arr[0] > k: return k

1l = 0
2r = len(arr) - 1
3while l < r:
4    mid = (l + r) // 2
5    x = arr[mid] if mid < len(arr) else 10**9
6    if x - mid - 1 >= k:
7        r = mid
8    else:
9        l = mid + 1
10
11return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1]

Java Solution

public int binarySearch(int[] arr) { if (arr[0] > k) { return k; }

1int l = 0;
2int r = arr.length - 1;
3while (l < r) {
4    int mid = (l + r) / 2;
5    int x = mid < arr.length ? arr[mid] : Integer.MAX_VALUE;
6    if (x - mid - 1 >= k) {
7        r = mid;
8    } else {
9        l = mid + 1;
10    }
11}
12
13return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];

}

Solution Implementation