458. Find Kth Positive Number Not in Array

Given a sorted array arr of distinct positive integers and an integer k, return the k-th positive integer that does NOT appear in arr. Positive integers start from 1.

Input: A sorted distinct positive integer array arr and integer k.

Output: The k-th positive integer not in arr.

Examples

Input: [3,5,7,9,11], 2
Output: 2
Explanation: Missing positives: 1,2,4,6,... 2nd is 2.

Input: [1,2,3,4,5,6], 3
Output: 9
Explanation: Missing: 7,8,9,... 3rd is 9.

Input: [2,4,6,8], 5
Output: 9
Explanation: Missing: 1,3,5,7,9,... 5th is 9.

Constraints

• 1 <= arr.length <= 10^3
• 1 <= arr[i] <= 10^3
• Distinct sorted
• 1 <= k <= 10^3

Asked by