diff options
Diffstat (limited to 'kth_missing_pos_num.c')
-rw-r--r-- | kth_missing_pos_num.c | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/kth_missing_pos_num.c b/kth_missing_pos_num.c new file mode 100644 index 0000000..db84e14 --- /dev/null +++ b/kth_missing_pos_num.c @@ -0,0 +1,26 @@ +// 1539. Kth Missing Positive Number +#include <stdio.h> + +/* + * given array 'arr' of positive integers sorted in a strictly increasing order, + * and an integer 'k', return 'kth' positive integer missing from array -- o(log + * n) + */ + +int findKthPositive(int *arr, int arr_size, int k) { + int l = 0, r = arr_size, m; + while (l < r) { + m = (l + r) / 2; + if (arr[m] - 1 - m < k) + l = m + 1; + else + r = m; + } + return l + k; +} + +int main() { + int a1[] = {2, 3, 4, 7, 11}, a2[] = {1, 2, 3, 4}; + printf("%d\n", findKthPositive(a1, 5, 5)); // expect: 9 + printf("%d\n", findKthPositive(a2, 2, 4)); // expect: 6 +} |