Author : shailesh_2004
Required Knowledge : Bit Manipulation, Greedy
Time Complexity :
Editorialists : shailesh_2004, nisritha35
Let us first check for which it is not possible to do so. Let us check for odd number
whose binary representation is
. We have to chose
such that their sum is
and xor is
. There should be odd number of
s in LSB place. This means that the sum will be odd which is wrong. Thus, for odd
it is not possible to find
which satisfy the given condition.
Now, let us consider power of . Take
as example whose binary representation is
. The number of
s in MSB place should be odd which can be
or
ones but
ones is not possible as the sum exceeds
. So, there has to be only one
in MSB place which leaves make
as
and
both as
. There is no other possible
which will satisfy the given constraints. But
can't be equal. So it is not possible for powers of
as well.
Consider three elements .
This triplet follows the given first condition and second condition but two numbers are equal.
To make them not equal, consider a position at which bit is set in and unset in
then swap these bits.
Here get's increased,
get's decreased and another
is constant. Hence these three values are not equal.
// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element
void solve()
{
ll n;
cin>>n;
if(n%2==1 || (n&(n-1))==0)
{
cout<<-1<<endl;
return;
}
ll a=n;
ll b=n/2;
ll c=n/2;
for(ll i=0;i<=62;i++)
{
if(((1LL<<i)&b)!=0 && ((1LL<<i)&a)==0)
{
a|=(1LL<<i);
b^=(1LL<<i);
break;
}
}
cout<<a<<" "<<b<<" "<<c<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll t;cin>>t;while(t--)
solve();
return 0;
}
To satisfy the conditions, we can analyze the binary representation of and examine how
,
, and
can be constructed bit-by-bit:
XOR Condition: The condition ^
^
=
requires that:
If a bit in
is
, then an odd number of bits in
,
, and
should be
at that position (either
or
of them should be set).
If a bit in
is
, then an even number of bits in
,
, and
should be
at that position (either
or
of them should be set).
Sum Condition: The sum implies that the total sum of bits in positions where
has a
must be achieved by either carrying over from the previous bit or by setting the bits in
,
, and
appropriately.
When calculating , the MSB of
will have a
in a position that’s higher than any bit in
. To satisfy the sum condition:
If a bit position in is
, we need a carry from the previous bit position to meet the sum requirement of
.
If a bit position in
is
, we either have zero or two bits set across
,
, and
at that position.
Start from the most significant bit and proceed bit by bit.
Use a carry variable to handle overflow across bit positions.
Assign values to ,
, and
based on the current bit configuration and the constraints.
To ensure
,
, and
are distinct, alternate assignments where possible.
// Author: D. Nisritha Reddy
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
using namespace std;
void solve(){
int n; cin >> n;
int carry = 0;
vi bits(63, 0);
for(int i = 62; i>=0; i--){
if((n&(1ll << i))) bits[i] = 1;
if(carry==1){
bits[i] += 2;
}
if((n&(1ll << i))) carry = 1;
else carry = 0;
}
if(carry){
cout << -1 <<"\n"; return;
}
bool first = true;
int a = 0, b = 0, c = 0;
for(int i = 0; i<63; i++){
if(bits[i]==0)continue;
else if(bits[i]==1)a += (1ll << i);
else if(bits[i]==3){
a += (1ll << i);
b += (1ll << i);
c += (1ll << i);
}
else{
if(first){
a += (1ll << i);
c += (1ll << i);
first = false;
}
else{
b += (1ll << i);
c += (1ll << i);
}
}
}
if(a==0 || b==0 || c == 0 || a==b || a==c || b==c){
cout << -1 <<"\n";
}
else{
cout << a <<" "<<b<<" "<<c<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1; cin>>t;
while(t--){
solve();
}
}