Nəsir və Bitwise OR Bərabər Massiv#12354

Nəsir və Bitwise OR Bərabər Massiv (Həll təhlili)

Problem Müəllifi:	Məhəmməd Nasser (MOAGEZA)
Hazırlayan:	Məhəmməd Nasser (MOAGEZA)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Ümumi Fikir: Biz yalnız OR əməliyyatından istifadə edərək bitləri artıra bilərik. Hər hansı bir elementin çata biləcəyi maksimum dəyər bütün elementlərin bitwise OR-u olmalıdır:

R = a_{1} ∣ a_{2} ∣ \dots ∣ a_{n}

R = a_1 \,|\, a_2 \,|\, \dots \,|\, a_n

Bütün elementləri bərabər etmək üçün hər biri $R$ olmalıdır. Artıq $R$ olan elementlər heç bir əməliyyata ehtiyac duymur. Digər bütün elementlər isə məhz bir əməliyyata ehtiyac duyur.

Beləliklə, minimum əməliyyat sayı belədir:

n - count (a_{i} = R)

n - \text{count}(a_i = R)

Bu həll hər test üçün $O (n lo g n)$ \mathcal{O}(n \log n) zaman çəkir.

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    map<int, int> mp;
    int res = 0;
    
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        mp[x]++;
        res |= x;
    }
    
    cout << n - mp[res];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << '\n';
    }
}