Practice › Binary Search
Kth Missing Positive Number
Easy · Binary Search · Asked at Meta, Amazon, Microsoft
The array is strictly increasing and contains positive integers. Print the k-th positive integer that is missing from it.
Input
First line: n. Second line: n integers. Third line: k.
Output
The k-th missing positive integer.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ a[i] ≤ 10^9
- 1 ≤ k ≤ 10^9
Example 1
Input
5 2 3 4 7 11 5
Output
9
Example 2
Input
4 1 2 3 4 2
Output
6
Hints
- Before index i, exactly a[i] − (i + 1) positive numbers are missing.
- That count never decreases, so binary search for how many array elements have fewer than k missing numbers before them.
Approach
missing(i) = a[i] − (i + 1) is non-decreasing. Find idx, the number of elements with missing(i) < k. All of those elements lie before the k-th missing number. The answer is then k + idx: counting up from 1, we skip one extra number for each such element.
Complexity: O(log n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &v : a) cin >> v;
long long k;
cin >> k;
int lo = 0, hi = n; // first index with missing(i) >= k
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] - (mid + 1) >= k) hi = mid;
else lo = mid + 1;
}
cout << k + lo << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
lo, hi = 0, n # first index with a[i] - (i + 1) >= k
while lo < hi:
mid = (lo + hi) // 2
if a[mid] - (mid + 1) >= k:
hi = mid
else:
lo = mid + 1
print(k + lo)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long k = sc.nextLong();
int lo = 0, hi = n; // first index with missing(i) >= k
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] - (mid + 1) >= k) hi = mid;
else lo = mid + 1;
}
System.out.println(k + lo);
}
}Solve Kth Missing Positive Number online · All practice problems