1060. Missing Element in Sorted Array

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

 

Example 1:

Input: A = [4,7,9,10], K = 1
Output: 5
Explanation: 
The first missing number is 5.

Example 2:

Input: A = [4,7,9,10], K = 3
Output: 8
Explanation: 
The missing numbers are [5,6,8,...], hence the third missing number is 8.

Example 3:

Input: A = [1,2,4], K = 3
Output: 6
Explanation: 
The missing numbers are [3,5,6,7,...], hence the third missing number is 6.

 

Note:

  1. 1 <= A.length <= 50000
  2. 1 <= A[i] <= 1e7
  3. 1 <= K <= 1e8

Rust Solution

struct Solution;

impl Solution {
    fn missing_element(nums: Vec<i32>, k: i32) -> i32 {
        let mut l = 0;
        let mut h = nums.len();
        while l < h {
            let m = l + (h - l) / 2;
            if nums[m] - nums[0] < k + m as i32 {
                l = m + 1;
            } else {
                h = m;
            }
        }
        nums[0] + l as i32 + k - 1
    }
}

#[test]
fn test() {
    let nums = vec![4, 7, 9, 10];
    let k = 1;
    let res = 5;
    assert_eq!(Solution::missing_element(nums, k), res);
    let nums = vec![4, 7, 9, 10];
    let k = 3;
    let res = 8;
    assert_eq!(Solution::missing_element(nums, k), res);
    let nums = vec![1, 2, 4];
    let k = 3;
    let res = 6;
    assert_eq!(Solution::missing_element(nums, k), res);
}

Having problems with this solution? Click here to submit an issue on github.