> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/1539.-kth-missing-positive-number.md).

# 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:**

<pre><code><strong>Input: arr = [2,3,4,7,11], k = 5
</strong><strong>Output: 9
</strong><strong>Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: arr = [1,2,3,4], k = 2
</strong><strong>Output: 6
</strong><strong>Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= arr.length <= 1000`
* `1 <= arr[i] <= 1000`
* `1 <= k <= 1000`
* `arr[i] < arr[j]` for `1 <= i < j <= arr.length`

&#x20;

## 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   
```

### Links

<https://leetcode.com/problems/kth-missing-positive-number/description/>

### Video Links

<https://www.youtube.com/watch?v=uZ0N_hZpyps&ab_channel=takeUforward>

### Approach 1:

```
n time
```

{% code title="C++" lineNumbers="true" %}

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

        return k;
    }
};
```

{% endcode %}

### Approach 2:

```
logn time
```

{% code title="C++" lineNumbers="true" %}

```cpp
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;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###