Codevita Previous Questions | Coin Distribution

Coin Distribution

LEVEL:Beginner

Description

Find the minimum number of coins required to form any value between 1 to N,both inclusive.Cumulative value of coins should not exceed N. Coin denominations are 1 Rupee, 2 Rupee and 5 Rupee.Let's Understand the problem using the following example. Consider the value of N is 13, then the minimum number of coins required to formulate any value between 1 and 13, is 6. One 5 Rupee, three 2 Rupee and two 1 Rupee coins are required to realize any value between 1 and 13. Hence this is the answer.However, if one takes two 5 Rupee coins, one 2 rupee coin and two 1 rupee coin, then too all values between 1 and 13 are achieved. But since the cumulative value of all coins equals 14, i.e., exceeds 13, this is not the answer.

Input Format

A single integer value.
Constraints:
0 < n < 1000

Output Format

Four space separated integer values.
1st - Total number of coins.
2nd - number of 5 Rupee coins.
3rd - number of 2 Rupee coins.
4th - number of 1 Rupee coins.

Example 1:

Input

Output

6 1 3 2

Example 2:

Input

Output

18 15 2 1

Example 3:

Input

Output

12 9 2 1

Approach

In order to get the number of fives we can use the formula which is given number - 4 divided by 5
now if given number- 5 multiplied by 5 is even then number of ones needed are only one else we only need one, one rupee coin
finally to get number of two coins we calculate the value of given number -5 * number of five rupee coins + number of ones subtracted from the given number

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Beginner

Coin Distribution

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Codevita Previous Questions

Beginner