Ctrl K

Cheapest Missing Numbers

Medium
The array taken holds numbers that are already in use (positive integers, possibly repeated). You must hand out count more numbers: they all have to be distinct positive integers that do not appear in taken. Pick them so that their sum is as small as possible and return that sum. Note that count can be very large, so handing the numbers out one at a time will not do.
Example 1
taken=[2, 5, 3], count=3 → 11

The free numbers are 1, 4, 6, 7, … The three smallest give 1 + 4 + 6 = 11.

Example 2
taken=[100, 100], count=4 → 10

Numbers 1, 2, 3, 4 are all free and sum to 10. The repeat in taken changes nothing.

Example 3
taken=[1, 2, 3], count=2 → 9

The first three numbers are taken, so we pick 4 and 5: the sum is 9.

Constraints
  • 1 ≤ len(taken) ≤ 10⁵
  • 1 ≤ taken[i] ≤ 10⁹
  • 1 ≤ count ≤ 10⁸
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsUp or Down for Every Post MediumRound Prices to a Total MediumThe Middle Bag MediumPrices That Fade With Each Sale MediumSame Prizes, Different Tastes Medium
loading Python…
Input
taken=[2, 5, 3], count=3
Expected
11

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.