PROBLEM LINK:
Setter: Kasra Mazaheri
Tester: Arshia
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Understanding of OR operation, Bit manipulation (here and here).
PROBLEM:
Given two integer L and R, find the maximum value of A | B for L \leq A, B \leq R where | denotes OR operation.
QUICK EXPLANATION
- Let us find the Most significant bit B position where bit L and R differ. Since L \leq R, L shall have this bit as 0 and R shall have this bit as 1.
- The maximum OR value we can obtain, when written in binary form has all bits significant than the B-th bit same as both L and R, and all bits from B-th bit shall be set.
EXPLANATION
Writing operands in binary form, OR operation sets ith bit ON if either of the operands has ith bit ON.
So, our aim is to have maximum number of bits set.
Now, consider binary representations of both L and R, from the most significant bit (MSB) to least significant bit (LSB).
Suppose the first x bits are the same for both L and R. Then all possible A and B have the first x bits the same as L and R, since even if a single bit among these x bits change, the value shall move outside range [L, R] which is not allowed.
Consider example,
001100010
001100110
In the above example, the first six bits are the same for both L and R, so all A and B such that L \leq A, B \leq R holds have these as first six bits and their OR too have these as first six bits.
Lemma: We can obtain all bits set after first x bits where the first x bits of L and R are the same.
Now, ignoring the first x bits, we found a mismatch at the bit. At this point, we can construct A such that the mismatched bit is not set for A and all bits less significant than the current bit is set. Similarly, We can construct B such that mismatch bit is set for B and all subsequent bits are not set in B.
Their OR shall have all bits including mismatch bit set.
Why such A is valid
Since we set all bits ON after mismatch bit in A, A is the largest number with mismatch bit off, and thus, is guaranteed to lie between range [L, R] as L has mismatch bit unset while R has mismatch bit set.
Why such B is valid
Since we set all bits OFF after mismatch bit in B, B is the smallest number with mismatch bit ON, and thus, is guaranteed to lie between range [L, R] as L has mismatch bit unset while R has mismatch bit set.
Applying this logic to our example, we have A = 001100011 and B = 001100100 and their OR is 001100111 which is maximum possible.
Hence, all we need to do is to find the Most significant mismatch bit which can be done by iterating from MST to LSB and comparing bits. Tutorials on Bit manipulation can be referred to in prerequisites.
TIME COMPLEXITY
Time complexity is O(log_2(R)) per test case.
SOLUTIONS:
Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int q;
scanf("%d", &q);
for (; q; q --)
{
ll l, r;
scanf("%lld%lld", &l, &r);
ll Mx = 0, i = 60;
for (; ~ i; i --, Mx |= (l & (1LL << i)))
if ((l ^ r) >> i & 1LL)
break;
Mx |= (1LL << (i + 1)) - 1;
printf("%lld\n", Mx);
}
return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int 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){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
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 readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
//=======================================================================//
const ll maxn=1e5+500;
const ll inf=1e9+800;
const ll mod=1e9+7;
ll solve(ll l,ll r,ll k){
if(k==1)return r;
ll ans=0;
for(ll i=0;i<62;i++){
if(!(((l>>i)&1)==0 && ((r>>i)&1)==0 && (r-l)<(1LL<<i))){
ans+=(1LL<<i);
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
t=readIntLn(1,(ll)1e5);
for(ll i=0;i<t;i++){
ll l,r;
l=readIntSp(0,(ll)1e18);
r=readIntLn(l,(ll)1e18);
cout<<solve(l,r,2)<<endl;
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class DOR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
long l = nl(), r = nl();
long ans = 0;
boolean f = false;
for(int b = 60; b >= 0; b--){
if(((l>>b)&1) != ((r>>b)&1))f = true;
if(f)ans |= 1l<<b;
else if(((l>>b)&1)==1)ans |= 1l<<b;
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new DOR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
.