This approach involves iterating through the array and maintaining a counter for missing positive integers. We start with the first positive number, which is 1, and determine if it is missing by comparing it to the current element in the array. If the number is missing, we decrement our k value. When k reaches zero, we have found our k-th missing number.
Time Complexity: O(n + k), where n is the length of the array. Space Complexity: O(1), as we are using constant extra space.
1#include <vector>
2using namespace std;
3
4int findKthPositive(vector<int>& arr, int k) {
5 int missing_count = 0;
6 int current = 1;
7 int i = 0;
8 while (missing_count < k) {
9 if (i < arr.size() && arr[i] == current) {
10 i++;
11 } else {
12 missing_count++;
13 if (missing_count == k) return current;
14 }
15 current++;
16 }
17 return -1; // this line is never reached
18}
19
20int main() {
21 vector<int> arr = {2, 3, 4, 7, 11};
22 int k = 5;
23 printf("%d\n", findKthPositive(arr, k));
24 return 0;
25}This solution uses a similar approach as the C solution. We iterate through the array, checking each expected number against the current number in the array. If they match, it's not missing, so we continue. Otherwise, we consider it as missing and check if it matches k.
By using binary search, a more efficient solution can be developed that reduces unnecessary checks. The key observation is that the number of missing integers before arr[i] can be calculated as arr[i] - (i + 1), which helps in deducing the position of the k-th missing number without iterating through every integer.
Time Complexity: O(log n), Space Complexity: O(1).
1def findKthPositive(arr, k):
2 left, right = 0, len(arr) - 1
3 while left <= right:
4 mid = left + (right - left) // 2
5 if arr[mid] - (mid + 1) < k:
6 left = mid + 1
7 else:
8 right = mid - 1
9 return left + k
10
11arr = [2, 3, 4, 7, 11]
12k = 5
13print(findKthPositive(arr, k))The Python solution follows a similar binary search approach. It calculates the number of missing numbers up to each midpoint in the array and uses that to refine the search for the missing k-th integer.