MAXOR

$2^k\leq N<2^{k+1}$을 만족하는 정수 $k$를 생각하자.

$1,2,4,\ldots,2^k$는 모두 $1$ 이상 $N$ 이하이므로 원하는 대로 고를 수 있다. 이 수들은 각각 서로 다른 하나의 비트만 가지고 있다. 따라서 이들을 적절히 골라 하위 $k+1$개 비트를 모두 로 만든

$$2^{k+1}-1$$

을 얻을 수 있다.

한편 $1$부터 $N$까지의 모든 수는 $2^{k+1}$보다 작다. 그러므로 어떤 수들을 XOR하더라도 $k+1$번째 이상의 비트가 $1$이 될 수 없고, 결과는 보다 클 수 없다.

따라서 답은 $N$보다 큰 가장 작은 $2$의 거듭제곱에서 $1$을 뺀 값이다. 시간 복잡도는 테스트 케이스마다 $O(\log N)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT6