September Long Challenge 2021

XOR Equal Solution September Challenge 2021

by

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.

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)

September Long Challenge 2021 Solution

Leave a Comment

three − 2 =