1539. Kth Missing Positive Number

Problem

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the k^th 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 5^th 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 2^nd 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

Personally, this felt like about a medium-difficulty problem.

Solution

impl Solution{
    pub fn find_kth_positive(arr:Vec<i32>, k:i32)->i32{
        let mut l:i32 = 0;
        let mut h:i32 = (arr.len()-1) as i32;
        while l<=h{
            let m = (l+(h-l)/2) as usize;
            let r = arr[m];
            // (m + 1) represents the expected value at index m because the values are in strictly increasing order.
            //r-(m+1) = r-m-1;
            let diff = r-(m as i32) -1;
            // Move diff closer to the target order k.
            if diff < k {
                l = (m as i32) + 1;
            } else {
                h = (m as i32) - 1;
            }
        }
        // l points to the index where k numbers are missing before it, so adding k gives the kth missing value.
        l+k
    }
}