COLLATZHD - 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? If yes, find the minimum number of moves needed.

EXPLANATION:

From the easy version, we know that the values of N that can reach 1 at all are:

  • N = 1, 2, 3, 6
  • Multiples of 4.

Among these, handling the four special cases is simple, so we only need to focus on the case where N is a multiple of 4.

Our operations now are adding 4 and dividing by 2.
However, we need to be careful when dividing by 2 - if we do it and end up no longer being a multiple of 4, we must end up at one of \{2, 6\} for 1 to remain reachable.

So, if N is a multiple of 4, but \frac{N}{2} is not a multiple of 4,

  • If \frac{N}{2} equals either 2 or 6 (so N = 4 or N = 12), it can be verified that it’s optimal to divide N by 2 and then reach 1 from there.
  • If \frac{N}{2} equals neither of these, we instead are forced to add 4; since moving to \frac{N}{2} would make it impossible to reach 1.

We thus only need to analyze the cases where \frac{N}{2} is itself a multiple of 4, or equivalently N is a multiple of 8.

We now have two options: either divide by 2, or add 4.
Observe that if we add 4, we will no longer be at a multiple of 8.
Thus, from what we saw above, we’re forced to immediately add 4 again to reach a multiple of 8.

This means that an optimal sequence of operations must either start with a division, or start with at least two addition operations.

However, observe that in an optimal sequence of operations, we’ll never perform two (or more) addition operations followed by a division.
This is because:

  • Two additions followed by a division transforms N to \frac{N+4+4}{2} = \frac{N}{2} + 4, with a cost of 3.
  • We could instead divide first and then add 4 to obtain \frac{N}{2} + 4 with a cost of 2.

This tells us that when N is a multiple of 8, it’s always optimal to divide by 2 immediately!

We thus have the following algorithm:

  • If N \in \{1, 2, 3, 6\}, return a precomputed answer.
  • If N is a non-multiple of 4 other than the above four values, return -1.
  • For multiples of 4,
    • If \frac{N}{2} \in \{2, 6\} or N is a multiple of 8, divide by 2.
    • Otherwise, add 4.

Simply implementing this recursively will lead to a runtime of \mathcal{O}(\log N) which is fast enough.
This is because we will use no more than two moves before dividing N by 2 (and maybe adding 2, but in particular note that the highest set bit of N will reduce so we obtain the \log bound anyway).

TIME COMPLEXITY:

\mathcal{O}(\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
ans = [-1]*20
ans[1] = 0
ans[2] = ans[3] = 1
ans[4] = ans[6] = 2

def solve(n):
    if n <= 6: return ans[n]
    if n%4 != 0: return -1
    
    if n%8 == 0 or n//2 <= 6: return 1 + solve(n//2)
    else: return 1 + solve(n+4)
    
for _ in range(int(input())):
    n = int(input())
    print(solve(n))
1 Like