# PROBLEM LINK:

Author: souradeep1999
Tester: mexomerf
Editorialist: iceknight1093

TBD

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)

1 Like

Weak testcases

https://www.codechef.com/viewsolution/1070609188

i used i inside the loop at line 99 instead of j and it still gave me an AC

1 Like

Site says learn cpp.

Edit: Btw, the compiler must’ve warned you:

suman@Skynet:~/Temp$g++ -o trash trash.cpp -std=c++17 -Wshadow -Wall -O2 -Wno-unused-result trash.cpp: In function ‘void solve()’: trash.cpp:95:21: warning: declaration of ‘i’ shadows a previous local [-Wshadow] 95 | for(int i = 0 ;i < 32; i++){ | ^ trash.cpp:91:13: note: shadowed declaration is here 91 | for(int i = 0 ; i < n; i++){ | ^ trash.cpp:99:22: warning: declaration of ‘i’ shadows a previous local [-Wshadow] 99 | for (int i = 0; i < 32; i++) | ^ trash.cpp:91:13: note: shadowed declaration is here 91 | for(int i = 0 ; i < n; i++){ | ^ suman@Skynet:~/Temp$


weak testcases
my code passed system testcases but failed my own testcases

int bit(int n) {
if (n == 0) return 1; // Edge case for zero, which needs at least 1 bit
return static_cast<int>(floor(log2(n))) + 1;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int tc;
cin>>tc;
while(tc--){
int n;cin>>n;
vi arr(n); read(arr,n);
vi bits(34,0);
int ans = arr[0];
for(int i=0;i<arr.size();i++){
if(arr[i]==0) continue;
bits[bit(arr[i])]++;
ans|=arr[i];
}
for(int i=31;i>=0;i--){
bits[i]+=bits[i+1];
}
int res = 0;
if(ans==0){
cout<<res<<endl;
continue;
}
for(int i=0;i<32;i++){
int x = ((1<<i)&ans);
if(x==0){
res = bits[i+1];
break;
}
}
cout<<res<<endl;
}
}

this was my code it passed system tc
but would fail on
1
2
19 4

ans is 2 but mine is giving 1
my friend also submitted a similar kind of approach in div2 contest tho we didnt cheat but still weak testcases

1
3
32 33 34
what should the answer be?

real bro
my code passed system testcases but failed my own testcases

int bit(int n) {
if (n == 0) return 1; // Edge case for zero, which needs at least 1 bit
return static_cast<int>(floor(log2(n))) + 1;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int tc;
cin>>tc;
while(tc--){
int n;cin>>n;
vi arr(n); read(arr,n);
vi bits(34,0);
int ans = arr[0];
for(int i=0;i<arr.size();i++){
if(arr[i]==0) continue;
bits[bit(arr[i])]++;
ans|=arr[i];
}
for(int i=31;i>=0;i--){
bits[i]+=bits[i+1];
}
int res = 0;
if(ans==0){
cout<<res<<endl;
continue;
}
for(int i=0;i<32;i++){
int x = ((1<<i)&ans);
if(x==0){
res = bits[i+1];
break;
}
}
cout<<res<<endl;
}
}

this was my code it passed system tc
but would fail on
1
2
19 4

ans is 2 but mine is giving 1
my friend also submitted a similar kind of approach in div2 contest tho we didnt cheat but still weak testcases

3 should be the ans

why not 1?

My bad

But it still doesn’t explain

https://www.codechef.com/viewsolution/1070743338

Getting an ac

1 Like

which 1 element you gonna remove

32

questions testcases are weak ,there are 300s of solutions that passed by just getting position of first zero from right in binary representation of or of all array elements.then removing all numbers greater than this.

for ex:
testcase
3
1 4 18

editorials code gives answer 2 .but
by logic of wrong code that passed
or of all elements of array=(1|4|18)===23
or in binary 10111
now position of first zero is 4 and wrong logic code removes the only greater element than 2^(4-1)=2^3=8 which is 18
and gives answer 1

almost one of every 3 solution i check by running manually on this testcase fails
which is accepted during contest.

3 Likes

1 0 0 0 0 1
1 0 0 0 1 0

then OR will be 100011 thats not 2^x-1

yeah same

is it possible to rerun all solutions for this question ?

1 Like

they should do it by themselves, CF is so smart on this, we can hack other’s solution and there is retesting of solutions after contest.

1 Like

i was writing solution thinking of countercases whole time,and wrong solutions passed wasted 1 hour on 2nd question only

same bro this was my first contest and this was div4’s 4th problem and i wasted my whole time resolving my own testcase
1
2
19 4

1 Like

btw noob question:

but how to approach (such or any) bitwise questions my mind just stops thinking while reading the ps and then finding the solution

Weak testcases!!!
Solution: 1070769511 (codechef.com)
Gave answer 1 for
3
17 2 4 still got accepted(should have given 3)