UQTEST - Editorial

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

  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[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 :smile: