Missing Element in Sorted Array

class Solution {
public:
    int findMissing(vector<int>& arr, int k) {
        int size = arr.size();
        
        for (int j = 1; j < size; ++j) {
            int gapCount = arr[j] - arr[j - 1] - 1;
            if (gapCount >= k) {
                return arr[j - 1] + k;
            }
            k -= gapCount;
        }
        
        return arr[size - 1] + k;
    }
};

This C++ solution efficiently finds the k-th missing element in a sorted array of integers. The process utilizes a straightforward approach:

• Initially, the size of the input array is determined.
• It then iterates through the array, checking the gap between consecutive elements.
• If the gap (missing numbers between two elements) is equal to or larger than k, the k-th missing element is calculated and returned immediately.
• If not, k is decremented by the number of elements found in that gap, and iteration continues.
• If the end of the array is reached without finding the k-th missing element, it is determined that the missing element lies beyond the last array element. The function then computes and returns this value by adding the remaining k to the last element of the array.

The function assumes that:

• The input array is non-empty.
• All numbers are sorted in ascending order without duplicates.
• The value of k is valid, meaning there are enough missing numbers to find the k-th missing one.

class Solution {
    public int findMissingKth(int[] array, int kth) {
        int length = array.length;
        
        for (int index = 1; index < length; ++index) {
            int missedNumbers = array[index] - array[index - 1] - 1;
            if (missedNumbers >= kth) {
                return array[index - 1] + kth;
            }
            kth -= missedNumbers;
        }
        
        return array[length - 1] + kth;
    }
}

This Java program effectively finds the k-th missing element in a sorted array. The array must be sorted for the method to function correctly, as it relies on the differences between consecutive elements to determine the number of missing integers between them.

• Begin by determining the length of the array.
• Iterate through the array starting from the first index. For each pair of consecutive elements, calculate the count of numbers that are missing between them.
• Compare the count of missed numbers to the k-th value you are searching for:
  • If the missed numbers at the current pair are equal to or more than k-th, calculate and return the exact k-th missing number using the starting element of the pair.
  • Otherwise, reduce the k-th value by the number of missed numbers and move to the next pair.
• If the loop completes and the k-th missing number isn't found within the array bounds, add k-th to the last element of the array to get the required missing number.

This solution ensures that you can efficiently find the missing element without having to construct additional data structures, making it time and space efficient.

class Solution:
    def findMissing(self, numbers: List[int], k: int) -> int:
        length = len(numbers)

        for index in range(1, length):
            missing_count = numbers[index] - numbers[index - 1] - 1
            if missing_count >= k:
                return numbers[index - 1] + k
            k -= missing_count

        return numbers[length - 1] + k

The provided Python3 code defines a solution to find the k-th missing element in a sorted array of numbers. The main function findMissing takes two parameters: numbers, which is a list of sorted integers, and k, the k-th missing number to find.

Here's a breakdown of how the function operates:

1. An integer length is calculated to get the total number of elements in the numbers list.
2. The function uses a loop to traverse through the numbers list starting from the second element (index 1).
3. Within the loop, it evaluates the count of missing numbers between the current number and the previous number using the formula (numbers[index] - numbers[index - 1] - 1).
4. If the count of missing numbers at the current position is greater than or equal to k, it means the k-th missing number is between the current and the previous number. Hence, the function returns the k-th missing number using the formula (numbers[index - 1] + k).
5. If the missing count at a particular index is less than k, the value of k is reduced by missing_count and the loop continues to the next iteration.
6. If the loop completes without returning (meaning the k-th missing number isn't between any elements of the array), the function assumes that the k-th missing number is beyond the highest number in the array. It calculates this by adding k to the last element in the array and returns the result.

This solution efficiently finds the k-th missing number using a combination of arithmetic operations and conditional logic, ensuring that the algorithm only iterates through the list once (O(n) time complexity).