# XOR Equal Solution September Challenge 2021

## 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:

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.

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)``````