Kth Missing Positive Number - Leetcode Solution

Problem:

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.

Example 1:

Input: arr = [2,3,4,7,11], k = 5 Output: 9 Explanation: The first missing positive integer is 1. The second missing positive integer is 5. The third missing positive integer is 6. The fourth missing positive integer is 8. The fifth missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2 Output: 6 Explanation: The first missing positive integer is 5. The second missing positive integer is 6.

Constraints:

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

Solution:

To solve this problem, we can use binary search technique. We can search for the missing positive integer in the given array using binary search. We start the search from the mid of the array. We use a variable count to keep track of the number of missing positive integers found so far. We can check the number of missing positive integers on the left of the mid by subtracting the value of mid from the value at the mid-1 index. If the number of missing positive integers found so far is less than k, we can move the left index to the mid + 1. Otherwise, we can move the right index to the mid - 1.

We can return the value at the left index as the kth missing positive integer if we have found k missing positive integers. Otherwise, we can return the value at the right index as the kth missing positive integer.

Here is the code for the solution:

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

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int missing = arr[mid] - mid - 1;

        if (missing < k) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left + k;
}

};

Time Complexity: O(log N), where N is the length of the array.

Space Complexity: O(1).

1