Nasser and Bitwise OR Equal Array#12354

Nasser and Bitwise OR Equal Array (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea: We can only increase bits using the OR operation. The maximum value any element can reach is the bitwise OR of all elements:

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

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

To make all elements equal, each must become $R$ . Elements already equal to $R$ need no operations. All other elements need exactly one operation.

Therefore, the minimum number of operations is:

n - count (a_{i} = R)

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

The solution runs in $O (n lo g n)$ \mathcal{O}(n \log n) time per test case.

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