Kth Missing Positive Number Solution in C++

Problem Description

Ah, the Kth Missing Positive Number problem! It’s like trying to find that one sock that mysteriously disappears in the laundry. You know it’s out there somewhere, but good luck finding it! In this delightful little challenge, you’re given a sorted array of positive integers and your task is to find the Kth positive integer that is missing from this array.

Imagine you’re at a party, and everyone is wearing a name tag with their favorite number. But wait! Some numbers are missing! You need to figure out which number is missing and which one is the Kth in line. Spoiler alert: it’s not as easy as it sounds!

Code Solution

class Solution {
 public:
  int findKthPositive(vector& arr, int k) {
    int l = 0;
    int r = arr.size();

    // Find the first index l s.t. nMissing(l) = A[l] - l - 1 >= k.
    while (l < r) {
      const int m = (l + r) / 2;
      if (arr[m] - m - 1 >= k)
        r = m;
      else
        l = m + 1;
    }

    // The k-th missing positive
    return l + k;
  }
};
    

Approach

The approach used in this solution is a binary search technique. The idea is to find the first index l such that the number of missing positive integers up to that index is at least k. The number of missing integers can be calculated as arr[m] - m - 1. Once we find this index, we can easily compute the Kth missing positive number using the formula l + k.

Time and Space Complexity

Time Complexity: O(log n) – The binary search reduces the search space logarithmically.

Space Complexity: O(1) – We are using a constant amount of space.

Real-World Example

Let’s say you’re organizing a marathon, and you have a list of registered runners. However, some runners decided to skip the event. You need to find out which runner number is missing, and you want to know the Kth missing runner number. This problem is akin to that scenario, where you’re trying to identify the missing numbers in a sequence.