Problem Statement

Given a sorted arrayarr of distinct positive integers and a positive integer k, return the kth missing positive integer that is missing from this sequence.

The missing numbers are the positive integers that do not appear in arr but are smaller than or equal to the maximum value reached by adding k missing numbers.

Examples

Example 1:

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

Explanation: The missing numbers are [1, 5, 6, 8, 9, 10, ...]
The 5th missing number is 9.

Example 2:

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

Explanation: The array contains no gaps until 4. The first missing number is 5, and the second missing number is 6.

Example 3:

Input: arr = [3, 6, 8, 10], k = 4
Output: 7

Explanation: The missing numbers are [1, 2, 4, 5, 7, 9...]
The 4th missing number is 7

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The problem revolves around finding the kth missing positive integer. Since arr is sorted and strictly increasing, the missing numbers between any two consecutive elements can be deduced. By iterating through the array and keeping track of the count of missing numbers, we can determine when the kth missing number is encountered.

Approach:

1. Start from 1 (the smallest positive integer).
2. Iterate through each number and check if it exists in the array:
   • If it does, skip it.
   • If it does not, count it as a "missing number."
3. Stop when k missing numbers are found.

This method effectively simulates the sequence of all positive integers and checks each one against the array.

Dry Run:

For arr = [2, 3, 4, 7, 11] and k = 5:

1. Start with current = 1. It is missing (missingCount = 1).
2. current = 2. It exists in the array.
3. current = 3. It exists in the array.
4. current = 4. It exists in the array.
5. current = 5. It is missing (missingCount = 2).
6. current = 6. It is missing (missingCount = 3).
7. current = 7. It exists in the array.
8. current = 8. It is missing (missingCount = 4).
9. current = 9. It is missing (missingCount = 5).

The 5th missing number is 9.

Code:

#include <iostream>
#include <vector>
using namespace std;

int findKthMissing(vector<int>& arr, int k) {
    int missingCount = 0; // Counter for missing numbers
    int current = 1;      // Start from the smallest positive integer
    int i = 0;            // Index in the array
    
    // Continue until we've found the kth missing number
    while (true) {
        if (i < arr.size() && arr[i] == current) {
            // If the current number is in the array, skip it
            i++;
        } else {
            // If the current number is missing, count it
            missingCount++;
            if (missingCount == k) {
                return current; // Return the kth missing number
            }
        }
        current++; // Move to the next number
    }
}

int main() {
    vector<int> arr = {2, 3, 4, 7, 11};
    int k = 5;
    cout << "The " << k << "th missing number is: " << findKthMissing(arr, k) << endl;

    return 0;
}

Complexity Analysis:

1. Time Complexity:
   • In the worst case, we iterate up to the kth missing number.
   • Each iteration involves checking whether the current number exists in the array (O(n) operation in the worst case for each lookup).
   • Overall, the time complexity is O(k × n).
2. Space Complexity:
   • No additional space is used apart from variables; hence it is O(1).

2️⃣ Binary Search

Intuition:

We can't apply classical binary search to it.

We can't apply binary search on answers as well because it is applicable when we are looking for minimum or maximum.

The sorted nature of the array suggests using binary search to optimize the solution. Instead of checking each number linearly, we focus on the count of missing numbers up to each index in the array.

For any arr[i], the count of missing numbers up to arr[i] is:

missing_count[i] = arr[i] - (i + 1)

This formula works because arr[i] includes the value at i, and (i + 1) represents the number of positive integers present up to arr[i] if no numbers were missing.

Using binary search, we:

1. Find the first position in the array where the missing count becomes greater than or equal to k.
2. The k-th missing number lies outside the current range or between the elements where the missing count changes.

Approach:

1. Calculate the missing count for midpoints during the binary search.
2. If the missing count at arr[mid] is less than k, the kkk -th missing number lies to the right.
3. Otherwise, it lies to the left.
4. Use the binary search result to calculate the exact kkk -th missing number.

Code:

#include <iostream>
#include <vector>
using namespace std;

int findKthMissing(vector<int>& arr, int k) {
    int left = 0, right = arr.size() - 1;

    // Perform binary search
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int missingCount = arr[mid] - (mid + 1);

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

    // At the end of the binary search, left points to the smallest index where missingCount >= k
    // Calculate the kth missing number
    return k + left;
}

int main() {
    vector<int> arr = {2, 3, 4, 7, 11};
    int k = 5;
    cout << "The " << k << "th missing number is: " << findKthMissing(arr, k) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(log n)
• Space Complexity: O(1)