A XOR operation

You are given a set S of distinct positive integers of size n (n is always even). Print the minimum positive integer k that is greater than 0 such that after replacing each element e of the set S with e⊕k, set S remains the same.

Print -1 if there is no such k.

Example:

Input:  n = 6, a[] = { 5, 6, 9, 10, 13, 14 }
Output: 3

Approach

Java


import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

public class XORTest {
    public static void main(String[] args) throws IOException {
        int t = 1;
        int n = 6;
        int a[] = { 5, 6, 9, 10, 13, 14 };
        System.out.println(getKay(a, n));
    }

    private static int getKay(int[] a, int n) {
        int b[] = new int[32];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int temp = a[i];
            set.add(temp);
            for (int j = 0; j < 32; j++)
                b[j] += ((temp >> j) & 1);
        }

        for (int i = 0; i < 32; i++)
            b[i] %= 2;

        int ans = 0;
        for (int i = 0; i < 32; i++)
            if (b[i] != 0)
                ans += (int) Math.pow(2, i);

        if (ans == 0)
            return -1;
        for (int i = 0; i < n; i++)
            if (!set.contains(a[i] ^ ans))
                return -1;
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int getKay(vector<int> a, int n)
{
    int b[32];
    for (int i = 0; i < 32; i++)
        b[i] = 0;
    set<int> st;
    for (int i = 0; i < n; i++)
    {
        int temp = a[i];
        st.insert(temp);
        for (int j = 0; j < 32; j++)
        {
            b[j] += ((temp >> j) & 1);
        }
    }

    for (int i = 0; i < 32; i++)
    {
        b[i] %= 2;
    }

    int ans = 0;
    for (int i = 0; i < 32; i++)
    {
        if (b[i] != 0)
            ans += pow(2, i);
    }

    if (ans == 0)
        return -1;
    for (int i = 0; i < n; i++)
    {
        //if not in set then return -1
        if (st.find(a[i] ^ ans) == st.end())
            return -1;
    }
    return ans;
}

int main()
{
    int n = 6;
    vector<int> a = {5, 6, 9, 10, 13, 14};
    cout << getKay(a, n) << "\n";
}


No comments:

Post a Comment