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 have the integer X.
You can subtract 3 from it if it’s greater than 3, or divide it by 2 if it’s even.
What’s the smallest it can become?
EXPLANATION:
The absolute smallest X can become is 1, so of course this should be our goal.
Let’s see when this is possible.
First, consider only being to subtract 3.
This will allow us to reach 1 from the values 1, 4, 7, 10, \ldots
In general, if X\bmod 3 = 1, i.e. X has a remainder of 1 when divided by 3, we can make it reach 1 by just subtracting 3 repeatedly.
This observation should also be a hint towards looking at different remainders modulo 3.
So, let’s consider what happens when X \bmod 3 = 2, i.e. the values 2, 5, 8, 11, \ldots
It’s not hard to see that these can also be made equal to 1 eventually: repeatedly subtract 3 till you reach X = 2, then divide that by 2 to obtain X = 1.
Finally, that leaves X\bmod 3 = 0, i.e. multiples of 3: the values 3, 6, 9, 12, \ldots
For these, observe that no matter what you do, X will always remain a multiple of 3.
- If you have a multiple of 3, and subtract 3 from it, it’s still a multiple of 3.
- If you have a multiple of 3, and divide it by 2, it’ll still be a multiple of 3.
This is because 2 and 3 are coprime to each other.
So, if X is initially a multiple of 3, it’ll always remain a multiple of 3.
This means the best we can do is to bring it down to 3 itself, which is of course always possible just using subtraction.
In the end, we have two simple cases:
- If X is a multiple of 3, the answer is 3.
- Otherwise, the answer is 1.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x = int(input())
if x%3 == 0: print(3)
else: print(1)