MAKENZERO - Editorial

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')
1 Like