Leetcode - Find Kth Positive Number

link

Problem

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.

Solution 1

Use binary search to find the gap where the Kth missing number exists

1. arr[i-1] = i
2. [ l , r )
3. m-1 is the midpoint of the subarray in the binary search

int findKthPositive(vector<int>& arr, int k) {
    size_t l = 0, r = arr.size();
    while(l < r){
        size_t m = (l + r + 1)/2 ;
        if(arr[m-1] - m < k){
            l = m;
        }else{
            r = m-1;
        }
    }
    //(l-1) + 1 + k
    return l + k;
}

Time Complexity : O(logn)

Solution 2

int findKthPositive(vector<int>& arr, int k) {
        int count = arr[0]-1;
        size_t i = 1;
        while(i < arr.size() && count < k){
            count += arr[i]-arr[i-1]-1;
            ++i;
        }
        if (count >= k){
            return i-1 + k;
        }
        return i + k;
}

Time Complexity : O(n)