---
tags: leetcode
---

# [1539. Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

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

        // Use binary search to find the smallest index, i, such that
        // arr[i] - i - 1 is greater than or equal k.
        // That is, k <= arr[i] - i - 1 is true.
        while (left < right) {
            int middle = left + (right - left) / 2;
            missing = arr[middle] - middle - 1;
            if (missing < k) {
                left = middle +  1;
            } else {
                right = middle;
            }
        }
        missing = arr[left] - left - 1;
        if (missing < k) {
            // The k-th missing integer shows up afer arr[left].
            //    arr[left] + (k - missing)
            // => arr[left] + (k - arr[left] + left + 1)
            // => arr[left] + k - arr[left] + left + 1
            // => left + k + 1
            return  left + k + 1;
        }

        // The k-th missing integer shows up before arr[left].
        //    arr[left] - (missing - k + 1)
        // => arr[left] - (arr[left] - left - 1 - k + 1)
        // => arr[left] - arr[left] + left + k
        // => left + k
        return left + k;
    }
};

## Time Complexity
$O(logn)$
$n$ is the length of `arr`.
## Space Complexity
$O(1)$
# Miscellane
<!--
# Test Cases

[2,3,4,7,11]
5

[1,2,3,4]
2

[2]
1

[2,3,5,6] 
2

[8,9]
1

[1,2]
8

[8,9]
1000

[2,3,5,6] 
8

* Wrong Answer: https://leetcode.com/submissions/detail/602585642/
-->