#### Hello Coders,

# As I know many of you were near to solution but got wrong answers in this question. Here is my solution and you can even ask your doubts in your logic here…

#### Problem link :

[Contest(div1)][1]

[Contest(div2)][2]

[Practice][3]

**Author :** [Yuri][4]

#### DIFFICULTY: Easy

#### Short description of problem :

Making XOR of N elements as big as possible by using integers from 1 to K.

#### Explaination :

First of we need to know the most significant bit which is 1 in binary representation of number K (i.e. the first bit which is 1 from left side) .

This, can be done in many ways… simplest way is taking \lfloor log_2(k) \rfloor +1 (i.e. taking its floor function which is, obviously, typecasted to int)

Now we have the position of Most Significant Bit, starting from rightmost bit.

(Alternate: It can also be done by a for loop (hint : using k/=2 and k\%2 ) )

Now the MAX XOR value we can achieve in best possible case is all 1's till (and including) the most significant bit.

**Example-** If position was 3 then MAX XOR we can achieve is-

111_2 **(in binary)** == 7 **in decimal**.

So basically MAX XOR is nothing but {2}^{(p)}-1 where p is position of MSB from right (1-based indexing) .

Note that, there can’t be any 1 at left side of MSB (Most Significant Bit) in binary representation in any number 1 to K , else the number will become >K, violating the conditions.

Taking an example-

## Click to view

#### Lets assume K to be 9 == 1001_2

#### then MAX XOR can be 1111_2 in binary… as simple as that…

#### In every case we can achieve the MAX XOR except some special cases like

#### 1)N==1 (answer is K)

#### 2)K==1 and N is even (answer is n times 1… hence XOR will be 0)

#### 3)K==2 and N is odd ( answer is 2 followed by (N-1) times 1’s… where XOR would be 2)

#### Otherwise XOR of all can be achieved as all the number of bits counted are 1…

**If your Output satisfies above explanation then your solution will definitely give** **AC**…

#### How to achieve MAX XOR for given N and K ?

Well there are many methods by which this can be done…

#### In fact only two numbers 1\leq number \leq K can achieve MAX XOR… and we can even make three numbers such that their XOR is the MAX XOR possible(i.e all 1's in binary).

### Let me explain you how…

If K = 9 = 00001001_2

then find temp = 00001000_2 (keep every bit except the leftmost bit which is 1 in K as 0).

code for which would be…

`temp = pow(2, (int) log2(k));`

1) Achieving MAX XOR by using Two numbers less than k is …

**temp \oplus temp-1 = 00001000_2 \oplus 00000111_2 = 00001111_2**.

2) Achieving MAX XOR by using Three numbers less than k is …

**temp \oplus temp-2 \oplus 1 = 00001000_2 \oplus 00000110_2 \oplus 00000001_2 = 00001111_2**.

#### which are MAX XOR…

$