FilesExpand file tree

master

/

min_number_of_coins_for_change.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

16 lines (16 loc) · 349 Bytes

master

/

min_number_of_coins_for_change.js

Copy path

Top

File metadata and controls

• Code
• Blame

16 lines (16 loc) · 349 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

// O(nd)time, O(n) space

function minNumberOfCoinsForChange(n, denoms) {

let res = new Array(n + 1).fill(Infinity);

res[0] = 0;

for (let i = 1; i <= n; i++) {

for (let d of denoms) {

if (d <= n) {

res[i] = Math.min(res[i], res[i - d] + 1);

}

}

}

if (res[n] === Infinity) {

return -1;

}

return res[n];

}