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 <stdio.h>
2
3int findKthPositive(int* arr, int arrSize, int k) {
4 int missing_count = 0;
5 int current = 1;
6 int i = 0;
7 while (missing_count < k) {
8 if (i < arrSize && arr[i] == current) {
9 i++;
10 } else {
11 missing_count++;
12 if (missing_count == k) return current;
13 }
14 current++;
15 }
16 return -1; // this line is never reached
17}
18
19int main() {
20 int arr[] = {2, 3, 4, 7, 11};
21 int k = 5;
22 printf("%d\n", findKthPositive(arr, 5, k));
23 return 0;
24}This C solution uses a simple iteration where it keeps track of what the next missing number should be while iterating over the array. It compares the current number to the next expected missing number. If the expected number is equal to the array number, it means the number is not missing, so it moves to the next array element. Otherwise, it increases the missing count and checks 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).
1#include <stdio.h>
2
3int findKthPositive(int* arr, int arrSize, int k) {
4 int left = 0, right = arrSize - 1;
5 while (left <= right) {
6 int mid = left + (right - left) / 2;
7 int missing = arr[mid] - (mid + 1);
8 if (missing < k) {
9 left = mid + 1;
10 } else {
11 right = mid - 1;
12 }
13 }
14 return left + k;
15}
16
17int main() {
18 int arr[] = {2, 3, 4, 7, 11};
19 int k = 5;
20 printf("%d\n", findKthPositive(arr, 5, k));
21 return 0;
22}This implementation uses binary search to efficiently find the k-th missing positive number. The search focuses on a "missing" variable that tells how many numbers are missing up to the mid-point in the array.