PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You have one five-rupee coin and an infinite number of one-rupee coins.
Find the minimum number of coins needed to pay exactly N rupees to a shop.
EXPLANATION:
If N \lt 5, we cannot use the five-rupee coin at all - so we must use one-rupee coins only.
The answer in this case is N.
If N \ge 5, then in order to minimize the number of coins used it’s optimal to always use the five-rupee coin.
The remaining amount must be paid using one-rupee coins.
So the answer in this case is
1 + N-5
Check whether N \lt 5 or N \ge 5 using an if condition and print the answer appropriately.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
n = int(input())
print(n if n < 5 else n-4)