Given an array arr of positive integers sorted in ascending order, and an integer k, find the kth positive integer that is missing from the array.
Table of Contents
Sample Input and Expected Output:
Input:
arr = [2, 3, 4, 7, 11]
k = 5
Output:
The 5th missing positive integer is: 9
Input:
arr = [1, 2, 3, 4]
k = 2
Output:
The 2nd missing positive integer is: 6
Solution in C++:
The idea is to use binary search to find the kth missing positive number. We start with two pointers left and right, representing the range of missing numbers. We calculate the number of missing integers between arr[left] and arr[right]. If this number is greater than or equal to k, we reduce the search space from the left side, otherwise from the right side. We repeat this process until we find the kth missing positive number.
#include <iostream>
#include <vector>
int findKthPositive(std::vector<int>& arr, int k) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int missingNumbers = arr[mid] - (mid + 1);
if (missingNumbers >= k) {
right = mid - 1; // Reduce search space from the left side.
} else {
left = mid + 1; // Reduce search space from the right side.
}
}
// At this point, the kth missing positive number is between arr[right] and arr[left].
return left + k;
}
int main() {
std::vector<int> arr1 = {2, 3, 4, 7, 11};
std::vector<int> arr2 = {1, 2, 3, 4};
int k1 = 5;
int k2 = 2;
int result1 = findKthPositive(arr1, k1);
int result2 = findKthPositive(arr2, k2);
std::cout << "The " << k1 << "th missing positive integer is: " << result1 << std::endl;
std::cout << "The " << k2 << "th missing positive integer is: " << result2 << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(log n), where n is the size of the input vector arr. This is because we use binary search to find the kth missing positive number, and each iteration reduces the search space by half.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The binary search is performed in-place without using any extra data structures.