# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Jeevan Jyot Singh

Tester: Istvan Nagy, Aryan

Editorialist: Vijay

# DIFFICULTY:

Easy

# PREREQUISITES:

Bit Manipulation

# PROBLEM:

JJ gives Chef a number X and challenges Chef to come up with three *distinct* numbers A, B, and C such that:

- 0≤A,B,C<2^{30};
- (A⊕B)+(B⊕C)+(C⊕A)=X.

Help Chef come up with three such numbers or determine that no such tuple exists.

Here, ⊕ denotes the bitwise XOR operation.

# EXPLANATION:

*Observation:* We can show that the parity of X cannot be odd. Suppose we define the parities of A,B
,C and then use the equation to obtain the parity of X.

*Case 1:* All are odd

In this case all the xor values will be even. Since the sum of even numbers is even. Thus X is even.

*Case 2:* Any two of the numbers are odd

In this case two of the pairs will give odd xor value and remaining even. Since the sum of two odd value is even . Thus X is even in this case also.

*Case 3:* Only one of the numbers is odd

In this case also two of the pairs will give odd xor value and remaining even. Thus X is even in this case also.

*Case 4:* All are even

In this case all xor values will be even . Thus X is even in this case also.

Now we know that answer does not exist for *odd values* of X. So,considering that *X is even* we can construct the tuples as follows.

Let’s say we choose one the numbers as 0.

I claim that this does not effect the existence of solution. Suppose some solution tuple (a,b,c) satisfying both conditions in the problem exist such that a>0,b>0 and c>0. Then we can always get another tuple with exactly one number equal to 0 by xoring all numbers with one of the number of tuple . Let’s say we choose to xor with c , then we will have (a⊕ c,b⊕ c,0) as c⊕ c=0 .

Now we can simplify our original equation by putting C=0.

We have , A + B+ A⊕ B =X … (1)

Let’s define S=X/2 and S' be the value of any set bit in S.

If there is only one set bit in S we cannot form a valid tuple otherwise we can always construct solution tuple by choosing tuple (S,S',0)

We can see that by choosing tuple (S,S',0) equation (1) becomes S+S'+S⊕ S'=2*S=X

Thus forming a valid tuple.

# TIME COMPLEXITY:

O(log(X)) depending upon the method used for finding the set bit.

# SOLUTION:

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define nline '\n'
void solve()
{
int x;
cin>>x;
if(x%2==1){
cout<<-1<<nline;
}
else{
for(int i=0;i<30;i++){
if(((1<<i)&(x/2)) && (x/2!=1<<i)){
cout<<(x/2)<<" "<<(1<<i)<<" "<<0<<nline; // cout<<S<<" "<<S'<<" "<<0<<nline;
return;
}
}
cout<<-1<<nline;
}
}
int main()
{
int t=1;
cin >> t;
while (t--)
{
solve();
}
}
```