Kth Missing Positive Number

Easy

Leetcode Link

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

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];

}

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know