LARGESTY - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093




Familiarity with bitwise OR


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.


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.


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


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 
const ll INF_ADD=1e18;  
#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;
#define debug(x);    
void _print(ll x){cerr<<x;}  
void _print(int x){cerr<<x;}  
void _print(char x){cerr<<x;}     
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
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){
    ll smallest=0;
    set<ll> need;  
    for(ll i=29;i>=0;i--){      
        ll found=0;
        for(auto it:a){ 
        if(found>=1 and found!=n){
    ll ans=0,done=0;
    for(ll i=29;i>=0;i--){
        if(done or smallest<i){
            if(ans+(1<<i) <= x){
            else if(need.count(i)){
    vector<ll> b=a;
    for(auto &it:b){
int main()                                                                                                     
    #ifndef ONLINE_JUDGE                        
    freopen("input.txt", "r", stdin);                                                  
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                          
    ll test_cases=1;                 
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)
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) {
        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;

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--) {

        if(cnt*n > 1e4) {

        if(!isPossible(v, i)) continue;
        else {

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

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
    x ^= (1<<idx)
    return x

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