Kaosar and XOR#12228

Kaosar and XOR (Editorial)

Problem Author:	Al Kaosar Hussain
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution You can write a brute force on $O (n^{2})$ \mathcal{O}(n^2) and observe the following :

For some integer $k$

{n = 2^{k} ⟹ 2^{k + 1} - 2 n \neq = 2^{k} ⟹ 2^{⌈ l o g_{2} (n)⌉} - 1

\displaystyle \begin{cases} n=2^k \implies 2^{k+1}-2 \\ n \neq 2^k \implies 2^{\lceil \log_2(n) \rceil}-1 \end{cases}

Proof :

Point 1 :

For some integers $n \leq 2^{m}$ n \le 2^m then all $1 \leq i, j \leq n$ 1 \le i,j \le n then all $popcnt (i \oplus j) < 2^{m}$ \text{popcnt}(i \oplus j) < 2^m

Point 2 :

Write $x$ in binary with at most $m$ bits. Let its highest set bit be at position $k < m$ k<m. Then choose $i = 2^{k}$ i=2^k , $j = i \oplus x$ j=i \oplus x , since $x < 2^{m}$ x<2^m , we've $j < 2^{m}$ j<2^m and because $n > 2^{m - 1}$ n>2^{m-1} thus $i \oplus j = x$ i \oplus j=x

Point 3 : For powers of 2 , same process happens with exclusion of the highest bit $(2^{m - 1})$ (2^{m-1}) , and Hence the answer is $2 n - 2$ 2n-2 in that case.


#if n=power of 2 then answer 2*n-2
#if n isn't power of 2 , 2^(ceil(log2(n))-1

MOD=10**9+7

p=[1]
cur=1
for i in range(1,62):
    cur*=2
    p.append(cur)
    
def solve():
    n=int(input())
    if(n==2):
        print(1)
        return
    if(n in p):
        print((2*n-2)%MOD)
    else:
        log=0
        while(n>0):
            n//=2
            log+=1
        print((pow(2,log,MOD)-1)%MOD)
for _ in range(int(input())):
    solve()

Python

Complexity $O (lo g (n))$ .