Codeforces 996A Hit the Lottery Solution & Explanation

Difficulty : 800

Problem Description

Allen has a LOT of money. He has n dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are 1, 5, 10, 20, 100. What is the minimum number of bills Allen could receive after withdrawing his entire balance?

Input

The first and only line of input contains a single integer n (1≤≤10⁹).

Output

Output the minimum number of bills that Allen could receive.

Examples

Note

In the first sample case, Allen can withdraw this with a 100 dollar bill, a 20 dollar bill, and a 5 dollar bill. There is no way for Allen to receive 125 dollars in one or two bills.

In the second sample case, Allen can withdraw two 20 dollar bills and three 1 dollar bills.

In the third sample case, Allen can withdraw 10000000 (ten million!) 100 dollar bills.

Solution

There have two common solution, the first solution is using a while loop to check.

• This method typically involves using a while loop to check if the remaining amount of money is greater than the denomination of the cash. If it is, the number of bills of that denomination is added to the result, and then the remaining amount is updated. However, it should be noted that using while loops and if conditions may result in poor time complexity.
• Second method employs a mathematical approach, calculating the required number of bills by continuously dividing the amount by denominations and finding the remainder. This method avoids the use of loops and conditional statements, potentially offering better performance in certain scenarios.

C# Solution

Solution1

int n = int.Parse(Console.ReadLine());
int cnt = 0;

cnt += n/100;
n = n%100;

cnt += n/20;
n = n%20;

cnt += n/10;
n = n%10;

cnt += n/5;
n = n%5;

cnt += n;

Console.WriteLine(cnt);

cnt += n; means to add the remaining amount to the total number of bills. In this case, if the remaining amount cannot be evenly divided by 100, 20, 10, and 5, then the remaining amount consists solely of 1-dollar bills, and it is added to the total number of bills.

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 996A – Codeforces

Random Codeforces Posts