# LARGESTY - Editorial

Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093

1823

# PREREQUISITES:

Familiarity with bitwise OR

# PROBLEM:

You’re given an array A containing at least two distinct elements, and an integer X.

For an integer 0 \leq Y \leq X, define the array B as B_i = A_i \mid Y.
Find the largest Y such that B consists of at least two distinct elements.

# EXPLANATION:

Since the operation we’re dealing with is bitwise OR, it helps to look at things bit-by-bit.

First, a useful definition: we say a bit b is set in the binary representation of integer x if the binary representation of x contains 2^b.
For example, 9 = (1001)_2 = 2^0 + 2^3 has bits 0 and 3 set, while bits 1, 2, 4, 5, 6, \ldots are not set.

Suppose we pick a Y and compute the array B, and there are two unequal elements; say B_i \neq B_j.
Then, in particular the binary representation of B_i and B_j must differ.
That is, there must exist a bit b which is set in the binary representation of B_i but not in B_j, or vice versa.

Without loss of generality, let’s say b is set in B_i and unset in B_j.
Then, we can observe the following:

• Y cannot have bit b set (otherwise it would be set in B_j = A_j \mid Y)
• This means A_i must’ve had bit b set, and A_j must’ve had it unset.

This tells us that for any valid Y, there will exist a bit b such that:

• b is unset in Y,
• Some element of A has this bit set, and
• Some element of A has this bit unset

Conversely, any Y that has such a bit b can easily be seen to satisfy the condition.

So, let’s fix the value of b and try to find the largest Y we can with respect to it; call this Y_b.
The answer is the maximum value of Y_b across all b.

Note that if b is such that:

• Every element of A has b set; or
• Every element of A has b unset

then b must be ignored, as per our rules above.
For a fixed b, this can easily be checked in \mathcal{O}(N) by iterating across all the elements.

Now the question is, how to find Y_b for a fixed b?
That can be done greedily.

• Iterate over bits from largest to smallest, i.e, from 29 down to 0.
• Initially, let Y_b = 0.
• Then, when processing bit i,
• If i = b, do nothing. This will ensure that Y_b doesn’t have bit b set, as required.
• Otherwise, if Y_b + 2^i \leq X, add 2^i to Y_b.
This way, we ensure that we never exceed X, while also making Y_b as large as possible.

So, for each b:

• We first check whether it is possibly valid, i.e, some element of A has it set and some other element has it unset.
This is done in \mathcal{O}(N).
• If it’s valid, we construct Y_b using the above algorithm. This is done in \mathcal{O}(30).

Since we do this for each bit from 0 to 29, the overall runtime is \mathcal{O}(30\cdot N + 30^2) which is good enough.

# TIME COMPLEXITY

\mathcal{O}(30\cdot N + 30^2) per test case.

# CODE:

Setter's code (C++)
#pragma GCC optimization("O3")
#pragma GCC optimization("Ofast,unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(int x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=200200;
void solve(){
ll n,x; cin>>n>>x;
vector<ll> a(n);
for(auto &it:a){
cin>>it;
}
ll smallest=0;
set<ll> need;
for(ll i=29;i>=0;i--){
ll found=0;
for(auto it:a){
found+=min(1ll,it&(1<<i));
}
if(found>=1 and found!=n){
need.insert(i);
}
}
assert(need.size()>=1);
smallest=*need.begin();
ll ans=0,done=0;
for(ll i=29;i>=0;i--){
if(done or smallest<i){
if(ans+(1<<i) <= x){
ans+=(1<<i);
}
else if(need.count(i)){
done=1;
}
}
}
vector<ll> b=a;
for(auto &it:b){
it|=ans;
}
sort(all(b));
assert(b[0]!=b[n-1]);
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}

Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for b in range(30):
ct = 0
for y in a: ct += (y >> b) & 1
if ct == 0 or ct == n: continue

cur = 0
for bit in reversed(range(30)):
if bit == b: continue
if cur + (1 << bit) > x: continue
cur += 1 << bit
ans = max(ans, cur)
print(ans)

1 Like

Quality questions. Good Editorial.

1 Like

Can we use binary search in this problem ???

i have tried to use binary search but only 2 test cases passed.

passed all test case with binary search


#include "bits/stdc++.h"
using namespace std;

#define int        long long int
#define now(x)     cout<<#x<<" : "<<x<<endl;

int MOD = 1e9 + 7;

bool isPossible(vector<int> arr, int y) {
int n = arr.size();
vector<int> b(n,0);

for(int i=0;i<n;i++) b[i] = arr[i] | y;

set<int> st;

for(auto i : b) {
st.insert(i);
if(st.size() == 2) return true;
}
return false;
}

void solve2(int n, int x, vector<int> v) {
int low = 0, high = x;

while(low <= high) {
int mid = low + ((high - low) >> 1);

if(isPossible(v, mid)) {
low = mid+1;
} else {
high = mid-1;
}
// cout<<low<<" "<<high<<endl;
}

// cout<<low <<" "<<high<<endl;
cout<<high<<endl;
}

void solve() {
int n, x; cin>>n>>x;
vector<int> v(n);
for(int i=0;i<v.size();i++){cin>>v[i];}

int cnt = 0;
for(int i=x;i >= 0;i--) {
cnt++;

if(cnt*n > 1e4) {
solve2(n,x,v);
break;
}

if(!isPossible(v, i)) continue;
else {
cout<<i<<endl;
break;
}
}
}

signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}


https://www.codechef.com/viewsolution/94753094

1 Like

What’s wrong with my solution?
I could not think of any wrong test cases.

def solve():
n, x = map(int, input().split())
a = [int(i) for i in input().split()]

for i in reversed(range(30)):
bit = (a[0]>>i) & 1
for j in range(n):
if (a[j]>>i)&1 != bit:
if (x>>i)&1 == 0: return x
idx = i
break

x ^= (1<<idx)
return x

for _ in range(int(input())):
print(solve())