Practice the most popular front-end questions asked in coding interviews with Frontend Churn

00:00:00

Given an array of `coins`

or denominations and a `target`

sum, calculate the minimum number of coins required to match the target. Note that the coins array will have denominations that are Infinitely available, i.e. coins can be repeated and added to calculate the target.

```
coins = [1, 2, 4]
target = 6
```

```
2
```

There are many ways to make target equal to `6`

using available coins of `[1, 2 , 4]`

.

- Adding
`$1`

coin`6 times`

. - Adding
`$1`

coin`4 tumes`

and`$2`

coins`2 times`

.

and so on till you get the minimum.

- Adding
`$4`

coin`1 time`

and`$2`

coin`1 time`

The `MINIMUM`

number of coins that can add up to the target sum is `2`

. This is obtained when we add `$4`

coin `1 time`

and `$2`

coin `1 time`

Therefore, the answer is = `2`

.

```
const coins = [2, 3, 7, 8]
const target = 27
```

```
4
```

The minimum number of coins required to make a target of 27 is `4`

. Which is obtained by adding `$8`

coin 3 times and `$3`

coin `1 time`

.

```
1 <= coins.length <= 10
1 <= coins[i] <= 100
1 <= target <= 1000
```

Click to reveal

Can you create an array of length = `target +1`

and somehow construct your solution from there on? Can you try iterating over the `coins`

array and see if you could use some mathematical formula to compute your results?

Click to reveal

Think Dynamic Programming, Think bottom-up solution. Solve for `ways[0]`

, build for `ways[target]`

Uploaded by: Manu Arora

Share this problem on