# EQBYXOR - Editorial

Setter: Jeevan Jyot Singh
Tester: Harris Leung
Editorialist: Trung Dang

1507

XOR

# PROBLEM:

JJ has three integers A, B, and N. He can apply the following operation on A:

• Select an integer X such that 1 \le X \lt N and set A := A \oplus X. (Here, \oplus denotes the bitwise XOR operation.)

JJ wants to make A equal to B.
Determine the minimum number of operations required to do so. Print -1 if it is not possible.

# EXPLANATION:

Let X = A \oplus B, and for the sake of editorialistâ€™s sanity we decrease N by 1. We now want to achieve X from XOR-ing as few elements no greater than N as possible.

There are 4 cases:

• X = 0. Answer is 0.
• X \le N. Answer is 1.
• \lfloor \log_2(X) \rfloor = \lfloor \log_2(N) \rfloor . Answer is 2. This semantically means the largest bit of X is equal to the largest bit of N, which means we can construct X by 2^{\lfloor \log_2(X) \rfloor} with some other value less than 2^{\lfloor \log_2(X) \rfloor}.
• Otherwise. Answer is -1. This happens in the case where the largest bit of X is larger to the largest bit of N, which means we cannot create this largest bit by any means.

# TIME COMPLEXITY:

Time complexity is O(1).

# SOLUTION:

Setter's Solution
``````#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}

string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

void solve()
{
int a = readIntSp(0, (1 << 30) - 1);
int b = readIntSp(0, (1 << 30) - 1);
int n = readIntLn(1, (1 << 30));
int z = a ^ b;
if(z == 0)
cout << 0 << endl;
else if(z < n)
cout << 1 << endl;
else
{
int msb = -1;
for(int i = 30; i >= 0; i--)
{
if(z >> i & 1)
{
msb = i;
break;
}
}
if((1 << msb) < n)
cout << 2 << endl;
else
cout << -1 << endl;
}
}

int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
ll a,b,n;cin >> a >> b >> n;
ll z=1;
while(z<n) z*=2;
if((a^b)==0) cout << "0\n";
else if((a^b)<n) cout << "1\n";
else if((a^b)<z) cout << "2\n";
else cout << "-1\n";
}
}
``````
Editorialist's Solution
``````#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int a, b, n; cin >> a >> b >> n; --n;
int x = a ^ b;
if (x == 0) {
cout << "0\n";
} else if (x <= n) {
cout << "1\n";
} else if (n != 0 && __lg(x) == __lg(n)) {
cout << "2\n";
} else {
cout << "-1\n";
}
}
}
``````
3 Likes

Whatâ€™s wrong with my code???

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define e cout<<"\n";
#define f(i,n) for(int i=0;i<n;i++)
int main(){
int T;cin>>T;
while(T--){
ll a,b,n,x,m;
cin>>a>>b>>n;

if(a==b){
cout<<0;e
}
else {

m = n;
a = a^b;
int i=0,j=0;
while(a){
i++;
a=a>>1;
}
while(n){
j++;
n=n>>1;
}
if(i<j){
cout<<1;e
}
else if(i==j && (m&(m-1)!=0)){
cout<<"2\n";
}
else{
cout<<"-1\n";
}
}

}
return 0;
}
``````

did not understand how the answer can be 2?

2 Likes

Suppose,
a = 7 â†’ 111
b = 1 ->001
n = 5, n-1 = 4, â†’ 100
We have to change 2 bits in a to b, we canâ€™t choose 110 to XOR as itâ€™s greater than n,
But we can choose 100 and 10, so two operations

4 Likes

My code will not print -1 .
1010 , 1001 both have 4th bit as most significant set bit so i==j is satisfied
and n!=power of 2, therefore the ans is 2.

Letâ€™s say n is 21, if a ^ b is 20 then the output should be 1.
Your code output will be 2.

Suppose a = 7, b = 18, a ^ b = 21 and N = 17.

Since N is lesser than a ^ b you canâ€™t choose x = 21 and get b in one operation.

In first operation, choose x = 16 (nearest power of 2 to (a ^ b), and it should be lesser than N, thatâ€™s why we are checking that log step) and xor it with a, a will become 21.
In 2nd operation choose x = 7 and xor it with a, a will become 18.

Dry run this case, you will get the intuition.

1 Like

bhava discord id dena tuzi . I have some doubts regarding my solution

``````test()
{
ll a,b,n;cin>>a>>b>>n;
ll xr=a^b;
ll rxr=rightSetBit(xr),rn=rightSetBit(n-1);
if(a==b)
cout<<0<<endl;
if(b==0)
cout<<1<<endl;
else if(n-1>=xr)
cout<<1<<endl;
else if(rxr==rn)
cout<<2<<endl;
else
cout<<-1<<endl;

}
``````

Can some one tell me which test case am i missing i was able to get partial marks for this.

can anyone explain me why the minimum operation canâ€™t be greater than 2 . also how are we checking that minimum operation is 2 . ??

1 Like

IMPORTANT OBSERVATION :

Decimal â†’ 2^n > (2^n)-1
Binary â†’ 1+(n zeros) > (n ones)

Example :
Decimal = 8
Binary = 1000
Here, 1000 > 0111

But, 1000 == 1000, and 1000 < 1001, of course in binary,
That says that if most significant bit of (a^b) differ, and is equal to most significant bit in n, then in 1 operation we can change the most significant bit only, and in another operation we can change all bits less than most significant oneâ€¦ so total 2 operations at max

I actually just hard coded,

``````#include <bits/stdc++.h>
#define int long long int

void solve(){
int a, b, n;
std::cin >> a >> b >> n;
int num = 1, val = 0;
std::vector <int> dp(32);
for(int i=0; i<32; i++){
if((a&1) != (b&1)){
dp[i] = 1;
val = num;
}
a >>= 1;
b >>= 1;
num <<= 1;
}
if(val >= n){
std::cout << "-1\n";
return;
}
int cnt = 0, sum = 0;
for(int i=31; i>=0; i--){
if(dp[i]){
if(sum + (1<<i) >= n){
cnt += 1;
sum = 0;
}
sum += (1<<i);
}
}
std::cout << (sum == 0 ? cnt : cnt+1) << "\n";
}

signed main() {

std::ios::sync_with_stdio(false);
std::cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

int t = 1;
std::cin >> t;
while(t--){
solve();
}
}
``````
1 Like

Discord nahiye bhava, ithech v4 ki

Let a = 7, b = 1, n = 5.

letâ€™s find x such that a ^ x = b
So, by using xor property we get x = a ^ b

Now, let say x > = n . So, we canâ€™t use x directly.

let x = d1 ^ d2
So, if d1 < n && d2 < n then, we can replace x by ( d1 ^ d2 )
a ^ ( d1 ^ d2 ) = b

So, all we have to find is, if there exist a pair ( d1 , d2 ) such that d1 < n && d2 < n

So, to find that we simply have to see if n-1 and x have same base of not ,because
the largest set bit of any of the d1 or d2 is equal to the largest set bit of x if
d1 ^ d2 =x.
Ex : let x =6 â€”> 110 if we want a (d1, d2) for x then think of it how we can generate it?
we must have the leftmost bits of d1 d2 be 0 and 1 such that 0 ^ 1= 1.
here d1 =4â€“>`1`00 d2 = 2â€“>`0`10 .
So, we have to do

1. a = a ^ d1
2. a ^ d2 So, two operationsâ€¦ ans = 2

If the base of x is greater than n-1 , then we know that one of the d1 or d2 have the largest set bit equal to the largest set bit of x .
means one of d1 or d2 will be greater than n-1. So, we have no solution.

2 Likes

are voice channel madhe sangitle aste tar clear zale aste . but still taku ka ithe code jo 30 points sathi accept zala hota. Mala mazi mistake mahitiye but ti resolve kashi karu te kalat nahiye

1 Like

Your logic is correct. i think the problem is here , rn=rightSetBit(n-1) let say x=1 and n=1. now answer should be -1, as x>n-1. but when you call for rightsetbit (depends on your implementation) it may be returning 0. and the rightmost set bit of x=1 is also zero, return 2 which is wrong.

Even though my code is running , there is a heavy flaw in constraints
In statement it is written 1 â‰¤ X < N , see the testcase
1
3 2 1
a=3 b=2 n=1
according to equality x=1 is not possible ,
also later in editorial it is written Xâ‰¤N. Answer is 1.
but judge is taking -1.

I feel like thatâ€™s a typo because everything else checks out

Hey, in the editorial I have decreased N by 1 at the start.

1 Like

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
int t;
cin>>t;
while(tâ€“){
int a,b,n;
cin>>a>>b>>n;
a=a^b;
if(a==0)
cout<<0;
else {
nâ€“; //X is till n-1
int m=n;
int z=a;
int i=0,j=0;
while(a){
i++;
a=a>>1;
}
while(n){
j++;
n=n>>1;
}
if(i>j)
cout<<-1;
else if(z<=m)
cout<<1;
else
cout<<2;
}
cout<<"\n";
}
return 0;
}
i==j does not always implies that ans could be 2.Eg-a=101 , n=110 . When a<=n then ans will be 1 otherwise it will be 2 .Eg a=110 ,b=101.

Can Someone explain testerâ€™s solution.