PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: souradeep1999
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array A. Find the minimum number of elements that need to be deleted so that the bitwise OR of the remaining elements equals 2^k - 1 for some non-negative integer k.
EXPLANATION:
We want the bitwise OR to equal 2^k - 1 for some integer k \geq 0.
Note that we don’t need to consider k \geq 31: all our elements are \leq 10^9 (which is less than 2^{30}), so their bitwise OR also cannot exceed 2^{30}.
This means we have only 31 values of k to worry about!
Let’s now fix the value of k (to something between 0 and 30), and try to find out the minimum number of elements that need to be deleted to get the bitwise OR to be exactly this 2^k - 1.
The integer 2^k - 1, when written in binary, has exactly the bits 0, 1, 2, \ldots, k-1 set.
So, any integer that has a bit \geq k set in it definitely must be deleted.
A simple criterion for this check is just that any integer \geq 2^k must be deleted.
Elements with only bits \lt k don’t need to be deleted.
Once everything with higher bits has been deleted, compute the bitwise OR of the remaining elements.
If this equals 2^k - 1, minimize the answer with the number of deleted elements; otherwise it’s impossible to reach this specific value of 2^k - 1 no matter what.
TIME COMPLEXITY:
\mathcal{O}(N\log\max A) or \mathcal{O}(\log\max A + N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define ordered_set tree<int, nuint_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=1000005;
#define M 1000000007
#define BINF 1e16
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 10000005
#define deb(xx) cout << #xx << " " << xx << "\n";
const int LG = 22;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int c = n;
for(int i = 0; i < 32; i++) {
int l = 0, x = 0;
for(int j = 0; j < n; j++) {
if(a[j] < (1LL << i)) {
l = l + 1;
x = x | a[j];
}
}
if(__builtin_popcountll(x + 1) == 1) {
c = min(c, n - l);
}
}
cout << c << endl;
}
#undef int
int main() {
#define int long long int
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("optput.txt", "w", stdout);
#endif
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}
int temp = 0;
int mn = n;
for(int i = 0; i < 40; i++){
int fin = 0;
int cnt = 0;
for(int j = 0; j < n; j++){
if(a[j] > temp){
cnt++;
}else{
fin |= a[j];
}
}
if(fin == temp){
mn = min(mn, cnt);
}
temp *= 2;
temp++;
}
cout<<mn<<"\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
ans = n
target, x = 0, 0
for i in range(n):
x |= a[i]
while target < x: target = 2*target + 1
if target == x: ans = n - i - 1
print(ans)
wasted 1 hour on 2nd question only