# Question

Formatted question description: https://leetcode.ca/all/1539.html

 1539. 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 1:

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.

Example 2:

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

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length


# Algorithm

### o(N)

A linear solution is because the title gives an array of positive integers in ascending order, and the array theoretically starts from 1. So ideally, the relationship between the number nums[i] and its corresponding subscript i should be nums[i] = i + 1. So when scanning the input array, if the difference between the number and its corresponding subscript is greater than 1, it means that the number is missing in the middle. When the gap is greater than or equal to K, the Kth missing number is found.

### o(logN)

Binary search. Because the input array is ordered, find the midpoint in mid, which is similar to the second approach, comparing the current number on the index with the difference between the index. If the difference is less than K, look for the right half of the array; otherwise, look for the left half of the array.

# Code

Java

Java

• class Solution {
public int findKthPositive(int[] arr, int k) {
List<Integer> list = new ArrayList<Integer>();
int length = arr.length;
int max = arr[length - 1];
int index = 0;
for (int i = 1; i < max; i++) {
if (arr[index] == i)
index++;
else
}
int size = list.size();
if (size >= k)
return list.get(k - 1);
else
return max + k - size;
}
}

• // OJ: https://leetcode.com/problems/kth-missing-positive-number/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int findKthPositive(vector<int>& A, int k) {
for (int i = 1, j = 0; i <= 2000; ++i) {
if (j < A.size() && A[j] == i) ++j;
else if (--k == 0) return i;
}
return -1;
}
};

• class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
if arr[0] > k:
return k
left, right = 0, len(arr)
while left < right:
mid = (left + right) >> 1
if arr[mid] - mid - 1 >= k:
right = mid
else:
left = mid + 1
return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)