Нассер і Побітове АБО Масиву Рівного#12354

Нассер і Побітове АБО Масиву Рівного (Розбір)

Автор задачі:	Мохаммед Нассір (MOAGEZA)
Підготував:	Мохаммед Нассір (MOAGEZA)
Редагував:	Хасан Салех (MathModel)

Розв'язок

Загальна ідея: Ми можемо лише збільшувати біти за допомогою операції OR. Максимальне значення, яке може досягти будь-який елемент, це побітове OR всіх елементів:

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

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

Щоб зробити всі елементи рівними, кожен з них повинен стати $R$ . Елементи, які вже дорівнюють $R$ , не потребують жодних операцій. Всім іншим елементам потрібна рівно одна операція.

Відтак, мінімальна кількість операцій дорівнює:

n - count (a_{i} = R)

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

Розв'язок працює за час $O (n lo g n)$ \mathcal{O}(n \log n) на тестовий випадок.

#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';
    }
}