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.
Solution
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];
}
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.