XOR Equal Solution
You are given an array A consisting of N integers and an integer X. Your goal is to have as many equal integers as possible in the array. To achieve this goal, you can do the following operation:
- Choose an index ii (1≤i≤N) and set Ai=Ai ⊕ X, where ⊕ denotes the bitwise xor operation.
Find the maximum number of equal integers you can have in the final array and the minimum number of operations to obtain these many equal integers.
Input Format
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each test case contains two lines of input.
- The first line of each test case contains two space-separated integers N,X.
- The second line of each test case contains N space-separated integers A1,A2,…,AN.
Output Format
For each test case, print a single line containing two space-separated integers – first, the maximum number of equal integers in the final array and second, the minimum number of operations to achieve these many equal integers.
Constraints
- 1≤T≤104
- 1≤N≤105
- 0≤X≤109
- 0≤Ai≤109
- The sum of N over all test cases does not exceed 5⋅105.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
3
3 2
1 2 3
5 100
1 2 3 4 5
4 1
2 2 6 6
Sample Output 1
2 1
1 0
2 0
Explanation
- Test case 1: One way to obtain 2 equal integers is to set A1=A1⊕2 =1⊕2=3. So the array becomes [3,2,3]. There is no way to obtain 3 equal integers in the final array.
- Test case 2: There is no way to obtain more than one equal integer.
SOLUTION
Program C: XOR Equal Solution in C
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
int t,n,x,i,j,ans,k,flag,max;
scanf("%d",&t);
while(t-->0){
scanf("%d %d", &n, &x);
int a[n*2],o[2*n],freq[2*n],c[2*n];
for(i=0;i<n;i++){
scanf("%d", &a[i]);
a[n+i] = a[i] ^ x;
o[i]=0;
o[n+i] = 0;
}
k=0;
ans = 0;
for(i=0;i<2*n;i++){
flag = -1;
if(i>=n){
if(a[i-n] == a[i])
continue;
}
for(j=0;j<k;j++){
if(a[i] == c[j]){
flag = 1;
freq[j]++;
if(i>=n)
o[j]++;
}
}
if(flag == -1){
c[k] = a[i];
freq[k] = 1;
if(i<n)
o[k] = 0;
else
o[k] = 1;
k++;
}
}
max = -1;
ans = 2*n + 1;
for(i=0;i<k;i++){
if(freq[i] > max){
max = freq[i];
ans = o[i];
}
else if (freq[i] == max){
if(ans > o[i])
ans = o[i];
}
}
printf("%d %d\n", max, ans);
}
return 0;
}
Program C++: XOR Equal Solution in C++
#include<bits/stdc++.h>
using namespace std;
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int test;
cin >> test;
while (test--) {
int n, k;
cin >> n >> k;
vector<int> v(n);
map<int, int> mp;
for (int i = 0; i < n; i++) {
cin >> v[i];
mp[v[i]]++;
}
int a = 0, b = INT_MAX;
for (auto x : v) {
if (x != x ^ k && a < mp[x] + mp[x ^ k]) {
a = mp[x] + mp[x ^ k];
b = mp[x ^ k];
}
else if (x != x ^ k && a == mp[x] + mp[x ^ k] && b > mp[x ^ k]) {
a = mp[x] + mp[x ^ k];
b = mp[x ^ k];
}
else if (a < mp[x]) {
a = mp[x];
b = 0;
}
}
cout << a << " " << b << endl;
}
}
Program Java: XOR Equal Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int T=sc.nextInt();
for(int t=0;t<T;t++){
int n = sc.nextInt();
long[] a = new long[n];
long x = sc.nextLong();
HashMap<Long,Long> h = new HashMap<>();
for(int i=0;i<n;i++){
a[i]=sc.nextLong();
if(h.get(a[i])!=null)
h.put(a[i],h.get(a[i])+(long)1);
else
h.put(a[i],(long)1);
}
long min=Integer.MAX_VALUE,max=0;
for(int i=0;i<n;i++){
long y = h.get(a[i]);
long z;
if(!h.containsKey(x^a[i]))
z=0;
else
z=h.get(x^a[i]);
if(a[i]==(x^a[i]))
z=0;
if(y+z>max){
max=y+z;
min=(long)Math.min(y,z);
}
else if(y+z==max)
min=(long)Math.min(min,Math.min(y,z));
}
System.out.println(max+" "+min);
}
}
}
Program Python: XOR Equal Solution in Python
from collections import defaultdict
for _ in range(int (input())):
a=defaultdict(lambda: 0)
b=defaultdict(lambda: 0)
c,c1=1,0
n,m = map(int, input().split())
arr=list (map(int, input().strip().split()))
for i in arr:
a[i] += 1
for i in arr:
if m != 0:
b[i^m] += 1
for i in arr:
if b[i] + a[i] > c:
c=b[i] + a[i]
c1=b[i]
if b[i]+a[i]==c:
c1=min(c1,b[i])
print(c,c1)