Coin ChangeMedium

Coin Change

Medium 18.9k45% acceptance

ArrayDynamic ProgrammingBreadth-First Search

You are given an array coins of distinct positive integers representing coin denominations, and an integer amount.

Return the fewest number of coins needed to make up exactly amount. You may use each denomination an unlimited number of times.

If that amount cannot be made up by any combination of the coins, return -1. (Making up 0 requires 0 coins.)

Example 1

Input: coins = [1,2,5], amount = 11

Output: 3

11 = 5 + 5 + 1, which uses three coins — no combination uses fewer.

Example 2

Input: coins = [2], amount = 3

Output: -1

Only even totals are reachable with a denomination of 2, so 3 is impossible.

Example 3

Input: coins = [1], amount = 0

Output: 0

Constraints

Asked atAmazonGoogleMicrosoftUber

JavaScript

⌘↵ to run

Loading editor…

Case 1

[1,2,5], 11

expected: 3

Case 2

[2], 3

expected: -1

Case 3

[1], 0

expected: 0

Case 4

[1,3,4,5], 7

expected: 2

Case 5

[2,5,10,1], 27

expected: 4

Case 6

[186,419,83,408], 6249

expected: 20

Case 7

[7], 14

expected: 2