DELXORONE - Editorial

editorial
, ,
1

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';
	}
}
4 Likes
2

This problem can also be solved by this approach.

For any two numbers x and y we must have xor(x, y) <=1, so we can say their binary representations excluding the 0th bit will be the same i.e.
(x >> 1) = (y >> 1).
So we can just find the minimum of n - cnt[x >> 1] for all distinct x present in the array.

The problem can even be generalized for pair xor lesser than (1 << k) , in that case ans will be min(n - cnt[val >> k]) for all vals present.

In case maximum pair xor is not a power of 2 then problem will get interesting and require further more thinking to solve.

2 Likes
3

I concluded that the numbers B1 xor B2 <= 1 means they should differ by 1 bit and jumped into writing code but I did not consider that they should differ by only last position bit

4 
#include <iostream>
#include <map>
#include <bits/stdc++.h>

using namespace std;

int main() {
	// your code goes here
	int t;
	cin >> t;
	while (t--) {
	    int N;
	    cin >> N;
	    int arr[N];
	    map<int, int> mp;
	    for (int i = 0; i < N; i++) {
	        int el;
	        cin >> el;
	        arr[i] = el;
	        mp[el]++;
	    }
	    int res = N;
	    for (auto const& [key, val] : mp){
	        int num = key ^ 1;
	        if (mp.find(num) != mp.end()) {
	            res = min(res, N - (mp[key] + mp[num]));
	        } else {
	            res = min(res, N - mp[key]);
	        }
	    }
	    cout << res << endl;
	}
	return 0;
}
5

I have a better approach which is quite simple two numbers xor will always be 0 or 1 only if the first number is even and the second number is even+1.
For example (2,3) and (4,5) and (6,7) this is the only possibility if we are trying to find two numbers.
Solution link for this approach - Solution

2 Likes