PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have the integer N. You can subtract either 3 or 4 from it in one move.
Can N be made 0?
EXPLANATION:
If N = 1 or N = 2 it’s definitely impossible, since 3 and 4 are larger than both.
If N = 5 you can also verify that it’s not possible to reach 0.
In every other case, it’s possible to reach 0.
To see why:
- N=3 and N=4 are obvious.
- 6 = 3+3, 7=3+4, 8=4+4 so all three can be made 0.
- For any N\gt 8, simply keep subtracting 3. Eventually you’ll reach one of 6,7,8 and be done.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n == 1 or n == 2 or n == 5: print('No')
else: print('Yes')