Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

5
2 3 4 7 11
5

Output

9

Example 2

Input

4
1 2 3 4
2

Output

6

Hints

  1. Before index i, exactly a[i] − (i + 1) positive numbers are missing.
  2. 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