SUBDIV - 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 have the integer N.
You can:

  • Subtract 2 from N, if it’s greater than 2.
  • Divide N by 2 if it’s even and greater than 1, i.e. set N to \frac{N}{2}, if it’s greater than 1.

How many distinct values are reachable using these operations?

EXPLANATION:

Suppose N is odd.
Then, we can’t divide it by 2, so our only option is to subtract 2 - but then it remains odd anyway, so our only option is again to subtract 2, and so on.
This means the only reachable values are N, N-2, N-4, \ldots, 5, 3, 1, i.e. all odd numbers \leq N.
There are \frac{N+1}{2} such numbers.

This leaves us with even N.
Clearly, by just using the “subtract 2” operation, we can reach all positive even numbers \leq N.
So, the only question is which odd numbers can be reached.

In fact, we only really care about the highest odd number that can be reached - since once this is known, all odd numbers smaller than it can be reached too, by just using the “-2” operation.

Further, we certainly must use the “divide by 2” operation to reach an odd number at all.
So, it can be seen that:

  • If \frac{N}{2} is odd, then it’s the largest odd number that can be reached is \frac{N}{2}.
    So, we can reach all odd numbers \leq \frac{N}{2}.
    There are \frac{\frac{N}{2} + 1}{2} such numbers.
  • Otherwise, \frac{N}{2} is even - meaning \frac{N}{2} - 1 is odd.
    It’s indeed possible to reach \frac{N}{2} - 1, since it equals \frac{N-2}{2} so we can first subtract 2 and then divide by 2.
    So, in this case we can reach \frac{\frac{N}{2}}{2} = \frac{N}{4} odd numbers.

In either case we have a formula in \mathcal{O}(1).

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    
    if n%2 == 1: print((n+1) // 2)
    else:
        if (n//2)%2 == 0: print(n//2 + n//4)
        else: print(n//2 + (n//2 + 1)//2)
2

for _ in range(int(input())):
n = int(input())

if n % 2 == 1:  # If n is odd
    print((n + 1) // 2)
else:  # n is even
    if (n // 2) % 2 == 0:  # Half of n is even
        print(n // 2 + n // 4)
    else:  # Half of n is odd
        print(n // 2 + (n // 2 + 1) // 2)