1539. Kth Missing Positive Number

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

Intuition

Approach:

We try to find smallest range in which an element may lie
Then we kind of find the number

eg->
        2 3 4 7 11
msg     1 1 1 3 6

how we found
idealy at position of 11, there should be 5 , So missing is 11-5

we want k=5th mssig
We get low at 11th, high=7th

So extra numbers we require are 2-> at high 3 are misssing for 5 we need 2

Hence 7+(2) = 9

Video Links

Approach 1:

n time

C++

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        for(auto &it: arr){
            if(it > k)
                break;
            else
                k++;
        }

        return k;
    }
};

Approach 2:

logn time

C++

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int low=0, high=arr.size()-1;

        while(low<=high){
            int mid = low+(high-low)/2;
            int missing = arr[mid] - (mid+1);

            if(missing >= k) high=mid-1;
            else    low=mid+1;
        }

        return high+1+k;
    }
};

Approach 3:

C++

Approach 4:

C++