Kth Missing Positive Number

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
181 upvotes
Asked in company
Athenahealth

Problem statement

You are given a strictly increasing array 'vec' and a positive integer 'k'.


Find the 'kth' positive integer missing from 'vec'.


Example : 
Input: vec = [2,4,5,7] , k = 3

Output: 6

Explanation : 
In the given example, first missing positive integer is 1 second missing positive integer is 3, and the third missing positive integer is 6.
Hence the answer is 6.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘n’ denoting the number of elements in 'vec'.

The second line contains ‘n’ space-separated integers denoting the elements of 'vec'.

The third line contains an integer ‘k’ denoting the 'kth' missing element.


Output Format : 
Print the 'kth' positive integer missing from 'vec'.


Note : 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
4
4 7 9 10
1


Sample Output 1 :
1


Explanation For Sample Input 1 :
The missing numbers are 1, 2, 3, 5, 6, 8, 11, 12, ……, and so on.
Since 'k' is 1, the first missing element is 1.


Sample Input 2 :
4
4 7 9 10
4


Sample Output 2 :
5


Expected Time Complexity :
Try to solve it in O(log(n)).

Constraints :

1 <= 'n' <= 10 ^ 4
1 <= 'k' <= 10 ^ 9
-10 ^ 9 <= 'vec[i]' <= 10 ^ 9

Time Limit : 1 sec
Hint

 Use the difference between the consecutive elements.

Approaches (2)
Single Array Traversal

First we remove the elements missing before the first number of the array which is trivial to check.

Then for each element check whether the current and next element is consecutive or not. If not, take the difference between the two and check till the difference is greater or equal to the given value of ‘k’. If the difference is greater, return current element - ‘count’.

Here is the algorithm :

  1. Run a loop from 0 to ‘n’ - 2 (say, iterator ‘i’).
  2. If ‘vec[i] + 1’ is not equal to ‘vec[i + 1]’, that is, elements are not consecutive, save their difference in a variable (say, ‘difference’) and decrement by one, which will give the count of absent elements between the elements ‘vec[i]’ and ‘vec[i + 1]’.
    • If the difference is lesser than ‘k’, deduct this difference from ‘k’. It means the missing element is not present between these 2 elements and the missing element count between these two elements is deducted
    • Else if the difference is greater than or equal to ‘k’, it means the missing element exists between the elements ‘vec[i]’ and ‘vec[i + 1]’. So, ‘vec[i]’ + ‘k’ will give the ‘k-th’ missing contiguous element in the given sequence starting from the leftmost element of the array. Turn ‘flag’ to ‘true’.
  3. If ‘flag’ is true, return the answer calculated in step 2b.
  4. Else, the answer will be greater than ‘vec[n - 1]’, so return ‘vec[n - 1]’ + ’k’.
Time Complexity

O(n), where ‘n’ is the number of elements in the array.

We traverse the whole array once. Hence, the overall time complexity will be O(n).

Space Complexity

O(1)

We use no extra space. Hence, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Kth Missing Positive Number
Full screen
Console