Practice/Meta/Leetcode 1539. Kth Missing Positive Number

Leetcode 1539. Kth Missing Positive Number

CodingMust

Problem

You are given a sorted array of distinct positive integers and an integer k. Your task is to find the k-th positive integer that does not appear in the array.

Positive integers start from 1, and the array is sorted in strictly increasing order. You need to determine which positive integer is the k-th one missing from the sequence.

Requirements

1. Return the k-th missing positive integer
2. The array contains distinct positive integers in strictly increasing order
3. Optimize your solution to run in O(log n) time complexity using binary search
4. Handle cases where the missing number is before, within, or after the array range

Constraints

• 1 ≤ arr.length ≤ 1000
• 1 ≤ arr[i] ≤ 10^9
• 1 ≤ k ≤ 10^9
• arr is sorted in strictly increasing order

Examples

Example 1:

Input: arr = [2, 3, 4, 7, 11], k = 5 Output: 9 Explanation: The missing positive integers are [1, 5, 6, 8, 9, 10, ...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1, 2, 3, 4], k = 2 Output: 6 Explanation: The missing positive integers are [5, 6, 7, 8, ...]. The 2nd missing positive integer is 6.

Example 3:

Input: arr = [5, 10, 15], k = 3 Output: 3 Explanation: The missing positive integers are [1, 2, 3, 4, 6, 7, 8, 9, 11, ...]. The 3rd missing positive integer is 3.