COLLATZEZ - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an integer N.
You can modify it as follows:

  • If N is odd, replace N by (3\oplus N) + 1.
  • If N is odd, replace N by either \frac{N}{2} or (3\oplus N) + 1.

Is it possible to make N reach 1?

EXPLANATION:

Let’s start by analyzing odd N, since our move there is forced.

We must change N to (3\oplus N) + 1.
Since XOR-ing by 3 only changes the lowest two bits of N (looking at its binary representation), let’s look at what happens with these two bits.
Note that looking at the lowest two bits of N is just the same thing as saying we look at N modulo 2^2 = 4 (in general, looking at the lowest k bits means looking at the number modulo 2^k).
N is presumed to be odd, and so we have two options modulo 4:

  1. N = 4k+1 for some integer k \ge 0.
    That is, the last two bits of N are \texttt{01}.
    Here, (3\oplus N) + 1 will set the last two bits of N to \texttt{11} and not change anything else.
    Essentially, N changes to N+2.
  2. N = 4k+3 for some integer k \ge 0.
    That is, the last two bits of N are \texttt{11}.
    Here, (3\oplus N) + 1 will set the last two bits of N to \texttt{01} and not change anything else.
    Essentially, N changes to N-2.

Observe that this pairs up all odd numbers into loops: for any k \ge 0, the values (4k+1) and (4k+3) will just endlessly cycle between each other, since the value after the transformation remains odd; hence all moves are forced.

So, it’s possible for an odd number to reach 1 if and only if either 4k+1 = 1 or 4k+3 = 1.
Equivalently, N = 1 or N = 3.

All odd numbers \gt 3 cannot reach 1 ever.

Next, let’s look at even numbers.
With the motivation from above, it’s helpful to consider them modulo 4.
We thus obtain:

  • If N = 4k, its last two bits are \texttt{00}.
    Here, the (3\oplus N)+1 operation will transform N to N+4.
    Importantly, N remains even, and a multiple of 4.
  • If N = 4k+2, its last two bits are \texttt{10}.
    Here, the (3\oplus N)+1 operation will leave N unchanged.

However, for even numbers, we have the additional option to divide by 2.

Note that when N = 4k+2, the only way we can change N at all is to divide it by 2.
However, upon dividing, it becomes 2k+1, which is odd.
So, this can reach 1 only when it equals 1 or 3; which means N must have been either 2 or 6 to begin with.

Finally, we have N = 4k, i.e. N being a multiple of 4.
Here, the (3\oplus N) + 1 operation allows us to add 4 to N.
Since N remains a multiple of 4 after this, we can essentially add 4 however many times we want before we start dividing.

This allows for us to always reach 1, because we can for example simply keep on adding 4 to N till we reach a power of 2 (which will be a multiple of 4, since it must be \ge 4 itself), and then simply repeatedly divide by 2 till we reach 1.

So, quite simply, the numbers that can reach 1 are:

  • 1, 2, 3, 6
  • All multiples of 4.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    if n%4 == 0 or n in [1, 2, 3, 6]: print('Yes')
    else: print('No')
3 Likes