## 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)

Contest(div2)

Practice

**Author :** Yuri

## 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…

## It is fact that if K>3 …

# 1 \leq temp , temp-1 , temp-2 \leq K (?Why… Think :D)

## Now you might be thinking why we just found two ways of maxing the MAX XOR with Two and Three numbers…

Because that was the main solution… Let me Explain that…

Now as we know

# y \oplus y = 0 and y \oplus 0 = y

which do you think is the number which all 1 to K will contain…( 1 itself isn’t it :D)

## Two cases :

# N is even :

```
print
(temp-1) (temp) (1) (1) (1)... n terms
```

# N is odd :

```
print
(temp-2) (temp) (1) (1) (1)... n terms
```

Obviously Don’t print brackets…

## So this is applicable when only K>3… (why not for k$\leq$3 ? take this as homework… )

We had already discussed partial answer for k=1,2,3…

Lets complete them…

### K==1

we don’t have any choice rather than printing 1’s …

### K==2

print 2 followed by (N-1) times 1 … (why? think…)

### K==3

N is odd : print 3 followed by (N-1) 1’s …

N is even : print 2 followed by (N-2) 1’s …