Xor it CodeChef Solution

Problem -Xor it CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

<<Previous CodeChef Problem Next Codechef Problem>>

Xor it CodeChef Solution in C++14

#include <iostream>
#include <algorithm>

using namespace std;

int n,k;

long long a[100001];
long long e[31];

int sol[10000000];
int solv;

int main()
{
    ios::sync_with_stdio(0);

    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a,a+n);

    int m(0);
    int en = 31;
    for(int i=30; i>=0; i--) {
        m |= 1<<i;

        long long db(1ll);
        for(int j = 1; j<n; j++) {
            if((a[j]&m) == (a[j-1]&m)) {
                db++;
            } else {
                e[i] += (db*(db-1)) / 2ll;
                db = 1ll;
            }
        }
        e[i] += (db*(db-1)) / 2ll;

        if(e[i] >= k) en = i;
    }

    if(en == 0) {
        for(int i=0; i<k; i++) {
            cout << "0 ";
        }
        cout << endl;
        return 0;
    }


    m = 0;
    for(int i=30; i>=en; i--) m |= 1<<i;

    for(int i=0; i<n; i++) {
        for(int j=i+1; (j<n) && ((a[j]&m)==(a[i]&m)); j++) {
            sol[solv++] = a[i]^a[j];
            if(solv > 10000000) return 101;
        }
    }

    sort(sol,sol+solv);

    for(int i=0; i<k; i++) {
        cout << sol[i] << " ";
    }
    cout << endl;

    return 0;
}

Xor it CodeChef Solution in C

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a,const void *b) {
	unsigned a1=*(unsigned *)a,b1=*(unsigned *)b;
	if (a1<b1) return -1; else if (a1>b1) return 1; else return 0;
}

unsigned a[100000];
unsigned b[600000];
int N,K;

int main() {
	int i, j, k, l;
	long long testcase;
	scanf("%d %d",&N,&K);
	for(i = 0; i < N; i++) scanf("%u", &a[i]);
	qsort(a, N, sizeof(a[0]), cmp);
	for(i = 0; i < 31; i++) {
		for(testcase = j = k = 0; j < N; j++) if ((a[j] >> i) != (a[k] >> i)) {
			testcase += (long long)(j - k)*(j - k -1) / 2;
			k = j;
		}
		testcase += (long long)(j - k)*(j - k -1) / 2;
		if (testcase >= K) break;
	}
	if (!i) {
		for(i = 0; i < K; i++) {
			if (1) putchar(' ');
			putchar('0');
		}
		puts("");
		return 0;
	}
	for(testcase = j = k = 0; j < N; j++) {
		if ((a[j] >> i) == (a[k] >> i)) for(l = k; l < j; l++) b[testcase++] = a[j]^a[l]; else k = j;
	}
	qsort(b, testcase, sizeof(b[0]), cmp);
	for(i = 0; i < K; i++) {
		if (i) putchar(' ');
		printf("%u", b[i]);
	}
	puts("");
	return 0;
}

Xor it CodeChef Solution in JAVA

import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractList;
import java.io.Writer;
import java.util.List;
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Egor Kulikov (egor@egork.net)
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		XorIt solver = new XorIt();
		solver.solve(1, in, out);
		out.close();
	}
}

class XorIt {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
		int count = in.readInt();
		int qty = in.readInt();
		int[] array = IOUtils.readIntArray(in, count);
		Arrays.sort(array);
		for (int i = 0; i <= 31; i++) {
			int mask = -(1 << i);
			int cnt = 0;
			int same = 1;
			for (int j = 1; j < count; j++) {
				if ((array[j] & mask) == (array[j - 1] & mask))
					cnt += same++;
				else
					same = 1;
			}
			if (cnt < qty)
				continue;
			if (i == 0) {
				int[] answer = new int[qty];
				out.printLine(Array.wrap(answer).subList(0, qty).toArray());
				return;
			}
			int[] answer = new int[cnt];
			int start = 0;
			int index = 0;
			for (int j = 1; j <= count; j++) {
				if (j < count && (array[j] & mask) == (array[j - 1] & mask))
					continue;
				for (int k = start; k < j; k++) {
					for (int l = k + 1; l < j; l++)
						answer[index++] = array[k] ^ array[l];
				}
				start = j;
			}
			Arrays.sort(answer);
			out.printLine(Array.wrap(answer).subList(0, qty).toArray());
			return;
		}
	}
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public static boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(outputStream);
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	}

class IOUtils {

	public static int[] readIntArray(InputReader in, int size) {
		int[] array = new int[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readInt();
		return array;
	}

	}

abstract class Array<T> extends AbstractList<T> {

	public static List<Integer> wrap(int...array) {
		return new IntArray(array);
	}

	protected static class IntArray extends Array<Integer> {
		protected final int[] array;

		protected IntArray(int[] array) {
			this.array = array;
		}

		public int size() {
			return array.length;
		}

		public Integer get(int index) {
			return array[index];
		}

		public Integer set(int index, Integer value) {
			int result = array[index];
			array[index] = value;
			return result;
		}
	}

	}

Xor it CodeChef Solution Review:

In our experience, we suggest you solve this Xor it CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Xor it CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Xor it CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn