Kth Missing Positive Number

You're given a sorted array of unique positive integers and an integer k. The array is strictly increasing, but it may be missing some positive numbers. Your task is to find the kth missing positive number in the sequence.

The array only contains some of the positive integers starting from 1, and some numbers are missing. You must figure out what the kth missing number would be if we continued counting all the positive numbers in order.

If the array is empty, then the answer is simply k because all numbers are missing.

Understanding the Problem

We are given a sorted array of distinct positive integers, and we are asked to find the k^th missing positive number.

To put it simply, we need to simulate counting from 1 upwards and identify which positive numbers are not present in the array. The kth number among those missing is our answer.

For example, consider the array [2, 3, 4, 7, 11] and k = 5. The missing numbers are [1, 5, 6, 8, 9, 10], so the 5^th missing number is 9.

Step-by-Step Solution with Example

step 1: Identify expected and actual values

At index i, the expected value is i + 1 if all numbers were present. But the actual value is arr[i]. So the total number of missing values up to index i is:

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

step 2: Iterate or use binary search

We traverse the array and for each index, calculate how many numbers are missing so far. If missingCount < k, we move forward. When we find the first index where missingCount ≥ k, we know the missing number lies before arr[i].

step 3: Use the previous value and compute the answer

If missingCount becomes ≥ k at index i, we use:

arr[i - 1] + (k - missingBeforePrevious)

This finds how many numbers we still need to add after the previous element to reach the kth missing.

step 4: Handle the case when all missing numbers are after the array ends

If the entire array is not missing enough values, the missing numbers are beyond the last element. Then the answer is:

arr[n - 1] + (k - totalMissing)

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

Index  Value  MissingCount
0      2      1 (1 is missing)
1      3      1 (no new missing)
2      4      1 (no new missing)
3      7      3 (5 and 6 are missing)
4      11     6 (8, 9, 10 are also missing)

At index 4, missing count is 6 ≥ 5, so kth missing lies before 11.
Previous value = 7, previous missing = 3
Still need 5 - 3 = 2 more steps → 7 + 2 = 9

Answer: 9

Edge Cases

• Array starts after 1: If the array starts from a number > 1, initial values are missing (e.g., [4, 5] → missing = [1, 2, 3])
• Array has no gaps: If array is like [1, 2, 3], the missing values begin after the end → kth missing = last + k
• Empty array: If the array is empty, kth missing = k itself
• k is small: Often the missing number lies before any actual gap. Be sure to check the first element.

Finally

This problem teaches us how to track missing values efficiently using either a loop or binary search. The key insight is to compare the expected count of numbers versus the actual values in the array. With this, we can find the exact position of the kth missing number without simulating the entire sequence.

Binary search gives us an efficient solution for large arrays with O(log n) time complexity, while linear scan also works fine for small inputs.

1. Initialize low = 0 and high = arr.length - 1.
2. While low ≤ high:
3. → Calculate mid = low + (high - low) / 2.
4. → Compute missing = arr[mid] - (mid + 1).
5. → If missing < k, search right side by setting low = mid + 1.
6. → Else, search left side by setting high = mid - 1.
7. Finally, return low + k as the answer.

#include <stdio.h>

int findKthPositive(int* arr, int n, int k) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int missing = arr[mid] - (mid + 1);
        if (missing < k)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low + k;
}

int main() {
    int arr[] = {2, 3, 4, 7, 11};
    int k = 5;
    printf("Kth missing number is: %d\n", findKthPositive(arr, 5, k));
    return 0;
}

#include <iostream>
using namespace std;

int findKthPositive(int arr[], int n, int k) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int missing = arr[mid] - (mid + 1);
        if (missing < k)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low + k;
}

int main() {
    int arr[] = {2, 3, 4, 7, 11};
    int k = 5;
    cout << "Kth missing number is: " << findKthPositive(arr, 5, k) << endl;
    return 0;
}

def findKthPositive(arr, k):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            low = mid + 1
        else:
            high = mid - 1
    return low + k

arr = [2, 3, 4, 7, 11]
k = 5
print("Kth missing number is:", findKthPositive(arr, k))

public class KthMissingNumber {
  public static int findKthPositive(int[] arr, int k) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      int missing = arr[mid] - (mid + 1);
      if (missing < k)
        low = mid + 1;
      else
        high = mid - 1;
    }
    return low + k;
  }
  public static void main(String[] args) {
    int[] arr = {2, 3, 4, 7, 11};
    int k = 5;
    System.out.println("Kth missing number is: " + findKthPositive(arr, k));
  }
}

function findKthPositive(arr, k) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    let missing = arr[mid] - (mid + 1);
    if (missing < k)
      low = mid + 1;
    else
      high = mid - 1;
  }
  return low + k;
}

const arr = [2, 3, 4, 7, 11];
const k = 5;
console.log("Kth missing number is:", findKthPositive(arr, k));

package main
import "fmt"

func findKthPositive(arr []int, k int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := low + (high-low)/2
        missing := arr[mid] - (mid + 1)
        if missing < k {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return low + k
}

func main() {
    arr := []int{2, 3, 4, 7, 11}
    k := 5
    fmt.Println("Kth missing number is:", findKthPositive(arr, k))
}

fn find_kth_positive(arr: &[i32], k: i32) -> i32 {
    let (mut low, mut high) = (0, arr.len() as i32 - 1);
    while low <= high {
        let mid = low + (high - low) / 2;
        let missing = arr[mid as usize] - (mid + 1);
        if missing < k {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    low + k
}

fn main() {
    let arr = vec![2, 3, 4, 7, 11];
    let k = 5;
    println!("Kth missing number is: {}", find_kth_positive(&arr, k));
}

fun findKthPositive(arr: IntArray, k: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val mid = low + (high - low) / 2
        val missing = arr[mid] - (mid + 1)
        if (missing < k)
            low = mid + 1
        else
            high = mid - 1
    }
    return low + k
}

fun main() {
    val arr = intArrayOf(2, 3, 4, 7, 11)
    val k = 5
    println("Kth missing number is: ${findKthPositive(arr, k)}")
}

func findKthPositive(_ arr: [Int], _ k: Int) -> Int {
    var low = 0, high = arr.count - 1
    while low <= high {
        let mid = low + (high - low) / 2
        let missing = arr[mid] - (mid + 1)
        if missing < k {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return low + k
}

let arr = [2, 3, 4, 7, 11]
let k = 5
print("Kth missing number is: \(findKthPositive(arr, k))")

function findKthPositive(arr: number[], k: number): number {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor(low + (high - low) / 2);
    const missing = arr[mid] - (mid + 1);
    if (missing < k) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low + k;
}

const arr = [2, 3, 4, 7, 11];
const k = 5;
console.log("Kth missing number is:", findKthPositive(arr, k));

Time complexity

Space complexity

O(1)

The algorithm only uses a constant number of variables regardless of input size.