In algorithmic challenges, especially in coding interviews and competitive programming, understanding the problem statement thoroughly is the first step toward coming up with an optimal solution. The problem “Kth Missing Positive Number” asks us to find the Kth missing positive number in a given list of numbers.

### Problem Description:

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.

#### Examples:

**Example 1:**

Input: `arr = [2,3,4,7,11], k = 5`

Output: `9`

**Example 2:**

Input: `arr = [1,2,3,4], k = 2`

Output: `6`

## Approaches to Solving the Problem

### 1. Brute-force Approach

One of the most straightforward ways to solve this problem is by employing a brute-force method where we simply iterate from `1`

upwards, checking whether each number exists in `arr`

. We keep a count of how many numbers we’ve found that are missing from `arr`

, and when this count reaches `k`

, we return the current number.

Here’s how you can implement this in Python:

```
def findKthPositive(arr, k):
count = 0
num = 1
while count < k:
if num not in arr:
count += 1
if count == k:
return num
num += 1
```

#### Time Complexity

The time complexity for this approach is O(n×m), where n is the value of the Kth missing positive number and mm is the length of `arr`

.

### 2. Optimized Approach Using Two Pointers

A more optimized way of solving this problem is by using two pointers to traverse the array `arr`

and the sequence of natural numbers. Since `arr`

is sorted, we can do this in a single pass.

Here’s how:

```
def findKthPositive(arr, k):
i, j = 0, 1
while k > 0:
if i < len(arr) and arr[i] == j:
i += 1
else:
k -= 1
if k > 0:
j += 1
return j
```

#### Time Complexity

The time complexity for this approach is O(n+m), where n is the length of `arr`

, and m is the value of the Kth missing positive number. This is more efficient than the brute-force approach.

### 3. Using Binary Search

Since `arr`

is sorted, we can also make use of binary search to find the range where the Kth missing positive number will reside.

Here’s the Python code for it:

```
def findKthPositive(arr, k):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
missing = arr[mid] - (mid + 1)
if missing < k:
left = mid + 1
else:
right = mid - 1
return left + k
```

#### Time Complexity

The time complexity for this approach is O(log n), where n is the length of `arr`

.

## Comparison of Approaches

## Conclusion

The problem of finding the Kth missing positive number can be solved using multiple approaches, each with its own trade-offs in terms of time and space complexity. By understanding the underlying mechanics of each approach, one can choose the most appropriate method for solving this problem efficiently.

For smaller datasets or less frequent queries, the brute-force or two-pointer approaches may be sufficient. However, for larger datasets or more frequent queries, the binary search approach will be more efficient.