# 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._

&#x20;

**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/](https://leetcode.com/problems/kth-missing-positive-number/description/)

### Video Links

[https://www.youtube.com/watch?v=uZ0N\_hZpyps\&ab\_channel=takeUforward](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

###

