[Solution] Dazzling AXNODR Challenge solution codechef

April 8, 2022 by admin

Dazzling AXNODR Challenge solution codechef – Dazzler has a blank canvas and $(N - 1)$ colours numbered from $2$ to $N$ .
Let $B$ denote the beauty of the canvas. The beauty of a blank canvas is $1$ .

[Solution] Dazzling AXNODR Challenge solution codechef

Dazzler paints the canvas by using all the $(N - 1)$ colours exactly once. On applying the $i^{t h}$ colour $(2 \leq i \leq N)$ :

If $i$ is odd, $B = B$ $&$ $i$ .
If $i$ is even, $B = B \oplus i$ .

Find the beauty of the canvas after applying all $(N - 1)$ colours.

Note: The colours are applied in ascending order. Colour number $2$ is applied first. The $i^{t h}$ numbered colour is applied after $(i - 1)^{t h}$ numbered colour for all $i > 2$ .

Here $&$ and $\oplus$ denote the bitwise AND and bitwise XOR operations respectively.

Input Format

First line will contain $T$ , the number of test cases. Then the test cases follow.
Each test case contains of a single line of input, a single integer $N$ .

Output Format

For each test case, output a single integer, the beauty of the canvas after applying all $(N - 1)$ colours.

[Solution] Dazzling AXNODR Challenge solution codechef

$1 \leq T \leq 10^{5}$
$2 \leq N \leq 10^{16}$

Sample Input 1

2
4
10

Sample Output 1

7
3

Dazzling AXNODR Challenge solution Explanation

Initially, $B = 1$ .

On applying colour $2$ : Since $2$ is even, $B = B \oplus 2 = 1 \oplus 2 = 3$ .
On applying colour $3$ : Since $3$ is odd, $B = B & 3 = 3 & 3 = 3$ .
On applying colour $4$ : Since $4$ is even, $B = B \oplus 4 = 3 \oplus 4 = 7$ .
On applying colour $5$ : Since $5$ is odd, $B = B & 5 = 7 & 5 = 5$ .
On applying colour $6$ : Since $6$ is even, $B = B \oplus 6 = 5 \oplus 6 = 3$ .
On applying colour $7$ : Since $7$ is odd, $B = B & 7 = 3 & 7 = 3$ .
On applying colour $8$ : Since $8$ is even, $B = B \oplus 8 = 3 \oplus 8 = 11$ .
On applying colour $9$ : Since $9$ is odd, $B = B & 9 = 11 & 9 = 9$ .
On applying colour $10$ : Since $10$ is even, $B = B \oplus 10 = 9 \oplus 10 = 3$ .

Test case $1$ : There are $3$ colours numbered $2, 3,$ and $4$ . Initially, $B = 1$ .
The final beauty of the canvas is $7$ .

Test case $2$ : There are $9$ colours numbered $2, 3, 4, 5, 6, 7, 8, 9,$ and $10$ . Initially, $B = 1$ .
The final beauty of the canvas is $3$ .

For Solution

“Click here“

Leave a Comment Cancel reply