In this Xor equal CodeChef problem solution, You are given an array AA consisting of NN integers and an integer XX. 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 i (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.
Problem solution in Python.
for t in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
d = dict()
for i in a:
if i not in d:
d[i] = 0
d[i] += 1
e = dict()
for i in a:
if i ^ x not in e:
e[i ^ x] = 0
e[i ^ x] += 1
ans = [0, 1000000000]
if x == 0:
print(max(d.values()), 0)
continue
for i in d:
temp = [d.get(i, 0) + e.get(i, 0), e.get(i, 0)]
if ans[0] < temp[0]:
ans = temp
elif ans[0] == temp[0]:
ans = min(ans, temp)
print(*ans)
Problem solution in Java.
import java.util.*;
import java.io.*;
import java.lang.*;
class codechef {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(
new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (Exception e) {
e.printStackTrace();
}
return str;
}
}
static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
static void sort(int[] a) {
ArrayList<Integer> l=new ArrayList<>();
for (int i:a) l.add(i);
Collections.sort(l,Collections.reverseOrder());
for (int i=0; i<a.length; i++) a[i]=l.get(i);
}
static long gcd(long a, long b) {
if (a == 0) return b;
return gcd(b % a, a);
}
public static void main(String[] args) throws Exception {
FastReader fs = new FastReader();
PrintWriter out = new PrintWriter(System.out);
int test = fs.nextInt();
while (test-- != 0) {
int n = fs.nextInt(), x = fs.nextInt();
int arr[] = new int[n];
HashMap<Integer, Integer> mp1 = new HashMap<Integer,Integer>();
HashMap<Integer, Integer> mp2 = new HashMap<Integer,Integer>();
for(int i =0; i<n; i++) {
arr[i] = fs.nextInt();
mp1.merge(arr[i], 1, Integer::sum);
if(x!=0) {
mp2.merge(arr[i]^x, 1, Integer::sum);
}
}
int max = 0, ans = Integer.MAX_VALUE, z = 0;
for(int k : mp1.keySet()) {
z = mp1.get(k) + mp2.getOrDefault(k, 0);
if(max<z) {
max = z;
ans = mp2.getOrDefault(k,0);
}
else if(max==z) {
ans = Math.min(ans , mp2.getOrDefault(k,0));
}
}
for(int k : mp2.keySet()) {
z = mp2.get(k);
if(max<z) {
max = z;
ans = z;
}
else if(max ==z) {
ans = Math.min(ans, z);
}
}
System.out.println(max + " " + ans);
}
out.close();
}
}
Problem solution in C++.
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
using namespace std;
using namespace chrono;
#define fast_io std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PI 3.14159265358979323844
#define mod 1000000007
#define pb push_back
#define pbk pop_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define tr(it,v) for(auto it=v.begin(),it!=v.end();it++)
#define fo(i,n) for(int i=0;i<n;i++)
#define rfo(i,n) for(int i=n-1;i>=0;i--)
#define sorta(v) sort(all(v))
#define mp make_pair
#define nl "n"
#ifndef ONLINE_JUDGE
#define db(x) cerr<<#x<<" = "; _dbgf(x);cerr<<nl;
#endif
typedef long long ll;
typedef double db;
vector<string> vs;
map<int,int> mi;
map<string,int> msi;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
void _dbgf(int x){cerr<<x;}
void _dbgf(double x){cerr<<x;}
void _dbgf(ll x){cerr<<x;}
void _dbgf(string x){cerr<<x;}
void _dbgf(long int x){cerr<<x;}
void _dbgf(char x){cerr<<x;}
void _dbgf(ull x){cerr<<x;}
template<class T,class V>void _dbgf(pair<T,V> p);
template<class T>void _dbgf(vector<T> v){cerr<<"[";for(T a:v){_dbgf(a);cerr<<" ";}cerr<<"]";}
template<class T>void _dbgf(set<T> s){cerr<<"[";for(T a:s){_dbgf(a);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _dbgf(map<T,V> m){cerr<<"[";for(pair<T,V> a : m){cerr<<a.first<<" : "<<a.second<<",";}cerr<<"]";}
template<class T,class V>void _dbgf(pair<T,V> p){cerr<<"{";_dbgf(p.ff);cerr<<",";_dbgf(p.ss);cerr<<"}";}
void solve(){
int n, x; cin >> n >> x;
map<int, int> m1,m2;
for (int i = 0; i < n; i++) {
int y; cin >> y;
m1[y]++;
if (x != 0) {
m1[y ^ x]++;
m2[y ^ x]++;
}
}
int equal = 0, operation = 0;
for (auto u : m1) {
if (u.second > equal) {
equal = u.second;
operation = m2[u.first];
} else if (u.second == equal) {
operation = min(m2[u.first], operation);
}
}
cout << equal << ' ' << operation << 'n';
}
int main(){
#ifndef ONLINE_JUDGE
freopen("error.txt","w",stderr);
#endif
fast_io;
long long t = 1;
cin>>t;
while(t--){
auto start1 = high_resolution_clock::now();
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
cerr<<"TIME: "<<duration.count()/1000<<nl;
#endif
}
return 0;
}
Problem solution in C.
#include <stdio.h>
int max (int arr[],int m,int arr1[]) {
int x=arr[0];
int y=0;
for(int i=1;i<m;i++) {
if(x<arr[i]) {
x=arr[i];
y=i;
}
if(x==arr[i]) {
x=arr[i];
if(arr1[i]<arr1[y])
y=i;
else
y= y;
}
}
return (y);
}
int temp;
void heapify(int arr[], int size, int i)
{
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < size && arr[left] >arr[largest])
largest = left;
if (right < size && arr[right] > arr[largest])
largest = right;
if (largest != i)
{
temp = arr[i];
arr[i]= arr[largest];
arr[largest] = temp;
heapify(arr, size, largest);
}
}
void heapSort(int arr[], int size)
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
for (i=size-1; i>=0; i--)
{
temp = arr[0];
arr[0]= arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
struct store {
int element;
int y;
};
int main(void) {
int q;
scanf("%d",&q);
while(q--) {
int n,x;
scanf("%d%d",&n,&x);
int arr[n];
struct store occurences[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
heapSort(arr,n);
int m,count=1;
m=0;
for(int j=0;j<n;j++) {
if(arr[j]==arr[j+1]) {
count++;
}
else {
occurences[m].element=arr[j];
occurences[m].y=count;
count=1;
m++;
}
}
int arr1[m],arr2[m];
for(int i=0;i<m;i++) {
arr1[i]= occurences[i].y;
arr2[i]= 0;
}
for(int j=0;j<m;j++) {
int k = occurences[j].element ^x;
for(int i=0;i<m;i++) {
if(k==occurences[i].element) {
if(x!=0) {
arr1[j]= occurences[i].y + occurences[j].y;
arr2[j] = occurences[j].y;
}
break;
}
}
}
int s = max(arr1,m,arr2);
printf("%d %dn",arr1[s],arr2[s]);
}
return 0;
}