LeetCode //C - 1539. Kth Missing Positive Number

1539. Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the $k^{th}$ positive integer that is missing from this array.
 

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,…]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,…]. The 2nd 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

From: LeetCode
Link: 1539. Kth Missing Positive Number

Solution:

Ideas:

1. Understanding the Problem Context:

• The sequence arr is sorted in strictly increasing order.
• The task is to identify the $k^{th}$ missing number from the sequence of all positive integers starting from 1, not just those represented in the array.

2. Initial Check Before the Array:

• Before even looking within the elements of the array, the code checks if the first element of arr is greater than k.
• If arr[0] (the first element) is more than k, it indicates that the $k^{th}$ missing number must be among the numbers from 1 to arr[0] - 1 (since the array starts at a number greater than k). Thus, the $k^{th}$ missing number in this case is simply k.

3. Checking Gaps Between Elements:

• As the array is processed starting from the first element, the code calculates the number of missing numbers up to each element compared to a continuous sequence of natural numbers.
• For each array element arr[i], it assesses the difference between arr[i] and arr[i-1] (previous element) to determine how many numbers are “missing” between them.
• The accumulated count of these missing numbers is tracked. If at any point this accumulated missing count reaches or exceeds k, the $k^{th}$ missing number can be directly calculated. It would be located precisely k numbers after the last accounted number (arr[i-1]) before the current arr[i].

4. Handling Missing Numbers After the Last Array Element:

• If after processing all elements of the array, the $k^{th}$ missing number hasn’t been found (i.e., if the cumulative missing numbers count is still less than k), it indicates that the $k^{th}$ missing number lies beyond the last element of the array.
• In this case, the $k^{th}$ missing number is computed as the last element of the array plus whatever remainder of k is still unaccounted for after considering all previous gaps.

Code:

int findKthPositive(int* arr, int arrSize, int k) {
    // Initial conditions when the array is empty or k is before the first element
    if (arrSize == 0 || k < arr[0]) {
        return k;
    }

    int missingCount = arr[0] - 1; // missing numbers before the first element
    if (missingCount >= k) {
        return k; // k-th missing number is before the first array element
    }

    // Check between the elements in the array
    for (int i = 1; i < arrSize; i++) {
        // Numbers missing between arr[i-1] and arr[i]
        int currentMissing = arr[i] - arr[i - 1] - 1;

        if (missingCount + currentMissing >= k) {
            // Calculate the exact k-th missing number
            return arr[i - 1] + k - missingCount;
        }

        // Update missing count
        missingCount += currentMissing;
    }

    // If k-th missing is beyond the last element
    return arr[arrSize - 1] + k - missingCount;
}