 # UQTEST - Editorial

Author: Bharat Thakur
Tester: Rishabh Rathi

MEDIUM

Bitwise XOR

# PROBLEM:

You are given two integers - L and R and you have to pick three integers (a, b, c) between [L,R] such that the conditions given hold or say that there are no such integers present

• L \leq a \leq b \leq c \leq R
• Bitwise XOR of any two integer is the third integer
• c−b is minimum possible
• If there are multiple possible values of a, b, c, then print the one with minimum b

Can you help find the three integers?

# EXPLANATION:

Lets go step by step, in the order of conditions

1. L \leq a \leq b \leq c \leq R - we know that XOR of same numbers is 0 and since L starts from 1 there will not be any tuple which has a=b or b=c or a=c.

2. If x ^ y = z, then y ^ z = x and x ^ z = y. This is a property of XOR. (^ is bitwise XOR)

1. Since numbers cannot be same, c-b will be greater than 0. So next minimum difference is 1 and for difference 1 we need adjacent integers between L and R.
We can iterate over them in O(n) time complexity and this can be proved that if a solution exists, then a solution of difference 1 will also exist.

2. Since we want minimum b, we can iterate over all pairs and find the one with minimum b.

# SOLUTIONS:

Setter's Solution (CPP)
#include <bits/stdc++.h>
using namespace std;

void solve() {
int l, r, m = INT_MAX;
cin >> l >> r;
pair<int, pair<int,int>> ans;

for(int i=l; i<r; i++) {
if((i^(i+1))>=l && (i^(i+1))<=r) {
if((i^(i+1))<m) {
m = i^(i+1);
ans = {m, {i,i+1}};
}
}
}
if(m!=INT_MAX) {
cout << ans.first << " ";
cout << ans.second.first << " ";
cout << ans.second.second << "\n";
}
else
cout << "-1\n";
}

int main() {
int t=1; cin >> t;
for(int i=1; i<=t; i++) {
solve();
}

return 0;
}

Tester's Solution (Python)
def solve(l, r):
diff = 10**8
b_min = 10**8
ans = [-1]

for i in range(l, r):
a = i ^ (i+1)
if l <= a <= r:
li = [a, i, i+1]
li.sort()

if li - li < diff:
diff = li - li
b_min = li
ans = li

elif li - li == diff:
if li < b_min:
b_min = li
ans = li

return ans

t = int(input())
for _ in range(t):
l, r = map(int, input().split())
ans = solve(l, r)
print(*ans)


Feel free to share your approach. In case of any doubt or anything is unclear, please ask it in the comments section. Any suggestions are welcome 