1847B - Hamon Odyssey - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename num_t>
using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename num_t1>
using multi_ordered_set = tree<num_t1, null_type, less_equal<num_t1>, rb_tree_tag, tree_order_statistics_node_update>;
 
// priority_queue<pair<int,int>, vector<pair<int,int> > , greater<pair<int,int> > > pq;
 
 
#define pb                     push_back
#define pie                    3.1415926535
#define inf                    1e18
#define mod                    1000000007
#define rall(x)                (x).rbegin(),(x).rend()
#define all(x)                 (x).begin(),(x).end()
#define int                    long long
#define endl                   '\n'
#define debug(x)               cout << '>' << #x << ':' << (x) << endl;
#define google(a,b)            cout << "Case #"<<(a)<<": "<<(b)<<endl;
 
void fast_io(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
 
void init_code(){
    fast_io();
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
 
/**********************************************************************************************************************************************************************************************************************************************************************/
// const int N=1e5+1;
// vector<int> sv(N);
// vector<int> prm;
 
// void sieve(){
//     for(int i=2;i*i<N;i++){
//         if(sv[i]==0){
//             for(int j=i*i;j<N;j+=i){
//                 if(sv[j]==0){
//                     sv[j]=i;
//                 }
//             }
//         }
//     }
 
//     for(int i=2;i<N;i++){
//         if(sv[i]==0){
//             prm.push_back(i);
//         }
//     }
// }
 
int find(int a,vector<int> &parent){
    vector<int> v;
    while(parent[a]>0){
        v.push_back(a);
        a=parent[a];
    }
    for(auto &i:v){
        parent[i]=a;
    }
    return a;
}
 
void merge(int a,int b,vector<int> &parent){
    a=find(a,parent);
    b=find(b,parent);
 
    if(a==b) return;
 
    if(abs(parent[a])>=abs(parent[b])){
        parent[a]+=parent[b];
        parent[b]=a;
    }
    else{
        parent[b]+=parent[a];
        parent[a]=b;
    }
}
 
int lcm(int a,int b){
    return a*b/(__gcd(a,b));
}
 
void fact(int n,vector<int> &f){
    vector<int> temp;
    f={1};
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            f.push_back(i);
            if(i!=n/i)
                temp.push_back(n/i);
        }
    }
    reverse(all(temp));
    for(auto &i:temp){
        f.push_back(i);
    }
    if(n!=1)
    f.push_back(n);
}
 
double pow(double a,int n){
    double ans=1.0;
 
    while(n>0){
        if(n&1){
            ans=ans*a;
        }
        a=a*a;
        n>>=1;
    }
    return ans;
}
 
/***********************************************************************************************************************************************************************************************************************************************************************/

// use pen and paper and write down the observations!!!!!



void solve(int T) {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    int mn = a[0];
    for(int i=1;i<n;i++){
        mn = (mn & a[i]);
    }

    vector<int> bitmn(32,0);
    for(int i=0;i<32;i++){
        int pw = (1ll << i);
        if((mn & pw) != 0){
            bitmn[i] = 1;
        }
    }

    vector<int> totalZero(32),temp(32);

    for(int i=0;i<32;i++){
        for(int j=0;j<n;j++){
            if(((1ll << i) & a[j]) == 0) totalZero[i]++;
        }
    }



    int ans = 1;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<32;j++){
            if((a[i] & (1ll << j)) == 0){
                temp[j]++;
            }
        }

        bool pos = true;
        for(int j=0;j<32;j++){
            if(temp[j] == 0){
                pos = false;
                break;
            }
        }

        if(pos){
            // debug(i);
            for(int j=0;j<32;j++){
                totalZero[j] -= temp[j];
                temp[j] = 0;

                if(bitmn[j] == 0 && totalZero[j] == 0){
                    cout<<ans<<endl;
                    return;
                }
            }

            ans++;
        }
    }

    cout<<ans<<endl;
}   
 
int32_t main() {
    init_code();
    int t;
    t=1;
    cin>>t;  
    for(int i=1;i<=t;i++){
        solve(i);
    }
    return 0;
}