PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given N.
You can modify it as follows:
- Add 1 to N, or
- Replace N with the next strictly larger multiple of 5.
Find the minimum number of operations needed to make N a multiple of 3.
EXPLANATION:
Observe that among N, N+1, N+2 - one of them will be a multiple of 3.
This is because, among any three consecutive numbers, one of them will be a multiple of 3.
(In general, among any K consecutive numbers, one of them will be a multiple of K.)
So, the answer is certainly at most 2: we start at N and keep adding 1 while it’s not a multiple of 3.
Thus, we only need to check if obtaining an answer smaller than 2 is possible - meaning either 0 or 1.
An answer of 0 is possible only when N is already a multiple of 3, which is easy to check.
An answer of 1 is possible only when (assuming the answer is not already 0), exactly one operation is performed.
We have a choice here: either add 1 to N, or shift it up to the nearest multiple of 5.
Simply try both options and check if either one is a multiple of 3.
If either one works, 1 is possible.
If both above checks fail, the answer is 2 since just two additions will work.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
if n%3 == 0: print(0)
else:
if (n+1)%3 == 0 or (n + (5-n%5))%3 == 0: print(1)
else: print(2)