PROBLEM LINK: Unique Test
Author: Bharat Thakur
Tester: Rishabh Rathi
DIFFICULTY:
MEDIUM
PREREQUISITES:
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
-
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.
-
If x ^ y = z, then y ^ z = x and x ^ z = y. This is a property of XOR. (^ is bitwise XOR)
-
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. -
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[2] - li[1] < diff:
diff = li[2] - li[1]
b_min = li[1]
ans = li
elif li[2] - li[1] == diff:
if li[1] < b_min:
b_min = li[1]
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