In this HackerEarth AND choice, problem-solution M is alone and he has an array a1,a2,..., an. M wants to choose two integers i,j such that i != j, 1 <= i,j <= n and the value ai & aj(bitwise AND) is maximum. What is the maximum value M can get?


HackerEarth AND choice problem solution


HackerEarth AND choice problem solution.

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

bool hv(int x, int b){
    return x & (1 << b);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;cin >> n;
    multiset<int> st;
    for(int i=0 ; i<n ; i++){
        int d;cin >> d;
        st.insert(d);
    }
    for(int bt=30 ; bt>=0 ; bt --){
        if(!hv(*st.rbegin(), bt))
            continue;
        auto it = st.rbegin();
        it ++;
        if(!hv(*it, bt)){
            int d = *st.rbegin();
            st.erase(st.find(d));
            d -= (1 << bt);
            st.insert(d);
            continue;
        }
        while(!hv(*st.begin(), bt))
            st.erase(st.begin());
    }
    cout << *st.rbegin() << "\n";
}

Second solution

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(29, -1, -1):
    cnt = 0
    ans |= 1 << i
    for x in a:
        if ans & x == ans:
            cnt += 1
    if cnt < 2:
        ans ^= 1 << i
print(ans)