XOR Equal Solution September Challenge 2021

Page Contents

Codechef XOR Equal 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 ii (1≤i≤N)(1≤i≤N) and set Ai=Ai⊕XAi=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.

Also See: September Long Challenge 2021 Solutions

Input Format

The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
Each test case contains two lines of input.
The first line of each test case contains two space-separated integers N,XN,X.
The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,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≤1041≤T≤104
1≤N≤1051≤N≤105
0≤X≤1090≤X≤109
0≤Ai≤1090≤Ai≤109
The sum of NN over all test cases does not exceed 5⋅1055⋅105.

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1

Sample Output 1

2 1
1 0
2 0

Explanation

Test case 11: One way to obtain 22 equal integers is to set A1=A1⊕2A1=A1⊕2 =1⊕2=3=1⊕2=3. So the array becomes [3,2,3][3,2,3]. There is no way to obtain 33 equal integers in the final array.

Test case 22: There is no way to obtain more than one equal integer.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program 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++:

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

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:

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)