Show problems as
Classic problem #330HardArrayGreedy

Patching Array

Real-world version: Minting Tokens To Cover Every Toll
Tracked in this browser only
Read Patching Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A toll plaza settles charges from a tray of tokens. values lists the face values of the tokens in the tray in non-decreasing order, and each token in the tray may be handed over at most once. Two tokens may carry the same face value, and each of them still counts as its own token.

An amount is settleable when some collection of the tokens on hand adds up to exactly that amount.

The plaza must be able to settle every amount from 1 to limit inclusive. To get there you may mint extra tokens: each minted token carries any positive integer face value you choose, you may mint several tokens carrying the same face value, and minted tokens join the tray and are also usable at most once each.

Return the smallest number of tokens you have to mint.

limit reaches 2^31 - 1, so a solution that walks through the amounts one at a time, or that builds anything sized by limit, will not finish.

Examples

Example 1

Input
values = [1, 2, 20], limit = 40
Output
3

Mint tokens of 4, 8 and 16. The tray then holds 1, 2, 4, 8, 16 and 20. Every amount from 1 to 31 is a sum of some of 1, 2, 4, 8 and 16, and every amount from 32 to 40 is the 20 plus an amount from 12 to 20, which those same five tokens supply.

Example 2

Input
values = [1, 2, 4, 8, 16], limit = 31
Output
0

Each amount from 1 to 31 is already a sum of some of the five tokens on hand, so nothing has to be minted.

Example 3

Input
values = [7, 9], limit = 6
Output
3

The tray cannot settle 1, 2 or 3, since its smallest token is 7. Minting 1, 2 and 4 leaves the tray holding 1, 2, 4, 7 and 9, and 1, 2, 1 + 2, 4, 1 + 4 and 2 + 4 settle the amounts 1 through 6.

Constraints

  • 1 <= values.length <= 1000
  • 1 <= values[i] <= 10^4
  • 1 <= limit <= 2^31 - 1
  • values is given in non-decreasing order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_tokens_to_mint(values: list[int], limit: int) -> int:
Java
public int minTokensToMint(int[] values, int limit)

More on the same topics