FIVECOIN - Editorial

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)