Kth Missing Positive Number

class Solution {
    public int kthMissingPositive(int[] sortedArr, int k) {
        int start = 0, end = sortedArr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (sortedArr[mid] - mid - 1 < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start + k;
    }
}

The given Java solution finds the kth missing positive number in a sorted array of integers.

• Understand that sortedArr is a sorted array of positive integers, and k is the kth missing position you want to find.

• The method kthMissingPositive uses a binary search approach to efficiently find the position by comparing and adjusting the start and end indices of the array based on the calculated missing elements count.

• Initialize two pointers, start as 0 and end as the last index of the array. Continue the search as long as start is less than or equal to end.

• Calculate the middle position, mid, using (start + end) / 2. Check the number of missing elements up to mid index using the formula (sortedArr[mid] - mid - 1).

• If this count is less than k, move the start index to mid + 1 to search in the right half of the array; otherwise, move the end to mid - 1 to search in the left half.

• The loop exits when the position is determined, and the kth missing number is given by start + k. This calculation adjusts for the gaps found during the binary search.

This approach ensures optimal efficiency in searching for the kth missing positive number, leveraging the sorted nature of the array with a time complexity of O(log n).

class Solution:
    def kthMissingNumber(self, numbers: List[int], k: int) -> int:
        start, end = 0, len(numbers) - 1
        while start <= end:
            middle = (start + end) // 2
            if numbers[middle] - middle - 1 < k:
                start = middle + 1
            else:
                end = middle - 1

        return start + k

The problem "Kth Missing Positive Number" is solved using a Python function kthMissingNumber in a class named Solution. This function takes two parameters: numbers, which is a sorted list of unique positive integers, and k, an integer representing the position of the missing number in the sequence that you need to find.

The approach implements a binary search mechanism to efficiently locate the k-th missing positive number. As the search progresses through the numbers list:

• Initialize start to 0 and end to the last index of numbers.
• Use a while loop to continue searching as long as start is less than or equal to end.
• Determine the middle index using (start + end) // 2.
• Calculate if the number of positive numbers missing before numbers[middle] is less than k.
• If so, adjust the start to middle + 1.
• Otherwise, adjust the end to middle - 1.
• After exiting the loop, calculate the k-th missing number by adding k to start and return this value.

This method effectively reduces the computational complexity compared to a naive approach, capitalizing on the properties of the sorted list and the nature of binary search. This achieves faster computation, dealing directly with the discrepancies between index positions and the actual numbers in the list.