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

l = 0
r = len(arr) - 1
while l < r:
    mid = (l + r) // 2
    x = arr[mid] if mid < len(arr) else 10**9
    if x - mid - 1 >= k:
        r = mid
    else:
        l = mid + 1

return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1]

Java Solution

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

int l = 0;
int r = arr.length - 1;
while (l < r) {
    int mid = (l + r) / 2;
    int x = mid < arr.length ? arr[mid] : Integer.MAX_VALUE;
    if (x - mid - 1 >= k) {
        r = mid;
    } else {
        l = mid + 1;
    }
}

return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];

}