PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author & Editorialist: Nishank Suresh
Testers: Takuki Kurokawa, Utkarsh Gupta
DIFFICULTY:
1516
PREREQUISITES:
Frequency arrays
PROBLEM:
Given an array A, find the minimum number of elements that need to be deleted from it so that the pairwise xor of any two elements in the resulting array is \leq 1.
EXPLANATION:
For each 0 \leq x \leq N, let freq(x) denote the frequency of x in A, i.e, the number of times it occurs. We’ll use this later.
First, let’s find out what the final array can look like.
Suppose it contains two elements x and y. Then, the condition tells us that either x\oplus y = 0 or x\oplus y = 1.
- If x\oplus y = 0, then the only possibility is that y = x.
- If x\oplus y = 1, then the only possibility is that y = x \oplus 1.
So, if the final array contains x, the only elements it can contain are x and x\oplus 1.
Suppose we fix x. Then, our only option is to delete every element that is not x or x\oplus 1.
Recall the frequency array we initially constructed: it tells us that the number of such elements is exactly N - freq(x) - freq(x\oplus 1).
The final answer is hence simply the minimum value of (N - freq(x) - freq(x\oplus 1)) across all 0 \leq x \leq N, which can be easily found by just iterating across x once freq has been precomputed.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> freq(n+10);
for (int i = 0; i < n; ++i) {
int x; cin >> x;
++freq[x];
}
int ans = n - 1;
for (int i = 0; i <= n; ++i) {
ans = min(ans, n - freq[i] - freq[i^1]);
}
cout << ans << '\n';
}
}