Cycle shifts#27

Cycle shifts (Editorial)

To shift a string $s$ to the right by $1$ we can add last digit to the beginning of $s$ , Formally if $∣ s ∣ = n$ |s|=n then :

shift to right (s) = s_{n} s_{1} s_{2} ... s_{n - 1}

\text{shift to right}(s)=s_ns_1s_2...s_{n-1}

We evaluate the binary representation of integer $n$ in $O (lo g (n))$ (call it $b$ ) and then we get the list of all possible shifts of $b$ in $O (∣ b ∣^{2}) = O (lo g^{2} (n))$ O(|b|^2)=O(\log^2(n)) after that we sort the list of shifts and we proceed the decimal represenation among max overall shifts

def f(s):
    return s[-1]+s[:-1] if s else s

n=int(input())
x=bin(n)[2:]
states=[x]
for i in range(len(x)-1):
    last=states[-1]
    states.append(f(last))
states.sort()
print(int(states[-1],2))

Python

Complexity $O (lo g^{2} (n))$ O(\log^2(n))