Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Learn Problem D. Coin Change | Problems
Dynamic Programming

Swipe to show menu

book
Problem D. Coin Change

The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.

The problem is to find the possible number of ways to get N cents with coins of different denominations. Imagine you have an infinite amount of coins valued c[0], c[1], c[2], …, c[m-1] – some values (for example, coins of 1, 2, 5, and 10 cents; these values are stored to input as an array).

You can combine these coins to achieve N cents in sum. Calculate the number of possible variations.

Order does not matter, i. e. for N=10 combinations 1+2+2+5, 2+1+2+5, and 5+2+1+2 are equal.

Example 1: N = 5, coins = [1,2,5] -> 4

There are 4 ways to combine coins: 5=1+1+1+1+1, 5=1+1+1+2, 5=1+2+2, 5=5.

Example 2: N=4, coins=[1,2,3,7] -> 4

Answer is 4: 4=1+1+1+1, 4=2+2, 4=1+3, 4=1+1+2

Example 3: N=100, coins = [1,3,5,7,10] -> 6426

Task

Swipe to start coding

Implement the function and call it for the given test calls.

  1. How many ways to reach the K coins if you know the number of how to reach K-c[0], K-c[1], ... , K-c[m-1] coins?
  2. What is the least sum you can change using only one coin of c[0], c[1], ..., or c[-1]?

Solution

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

SectionΒ 2. ChapterΒ 4
single

single

Ask AI

expand

Ask AI

ChatGPT

Ask anything or try one of the suggested questions to begin our chat

close

Awesome!

Completion rate improved to 8.33

book
Problem D. Coin Change

The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.

The problem is to find the possible number of ways to get N cents with coins of different denominations. Imagine you have an infinite amount of coins valued c[0], c[1], c[2], …, c[m-1] – some values (for example, coins of 1, 2, 5, and 10 cents; these values are stored to input as an array).

You can combine these coins to achieve N cents in sum. Calculate the number of possible variations.

Order does not matter, i. e. for N=10 combinations 1+2+2+5, 2+1+2+5, and 5+2+1+2 are equal.

Example 1: N = 5, coins = [1,2,5] -> 4

There are 4 ways to combine coins: 5=1+1+1+1+1, 5=1+1+1+2, 5=1+2+2, 5=5.

Example 2: N=4, coins=[1,2,3,7] -> 4

Answer is 4: 4=1+1+1+1, 4=2+2, 4=1+3, 4=1+1+2

Example 3: N=100, coins = [1,3,5,7,10] -> 6426

Task

Swipe to start coding

Implement the function and call it for the given test calls.

  1. How many ways to reach the K coins if you know the number of how to reach K-c[0], K-c[1], ... , K-c[m-1] coins?
  2. What is the least sum you can change using only one coin of c[0], c[1], ..., or c[-1]?

Solution

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

close

Awesome!

Completion rate improved to 8.33

Swipe to show menu

some-alt