1539. 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