Skip to content

Latest commit

 

History

History

1539 - Kth Missing Positive Number

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1539. Kth Missing Positive Number share

Problem Statement

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

Return 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

 

Follow up:

Could you solve this problem in less than O(n) complexity?

Click to open Hints

  • Keep track of how many positive numbers are missing as you scan the array.

Solutions

impl Solution {
    pub fn find_kth_positive(arr: Vec<i32>, k: i32) -> i32 {
        let (mut l, mut r) = (0, arr.len());

        while l < r {
            let mid = l + (r - l) / 2;

            if arr[mid] - mid as i32 - 1 >= k {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        l as i32 + k
    }
}