Avengers: Assemble the Array

Author : R.i.s.h.i_99

Required Knowledge : Bit Manipulation

Time Complexity : $\mathcal{O}(3\cdot N)$

Editorialist : R.i.s.h.i_99

Approach:

First, let us try to understand how to determine whether it is possible to make at least two stones have equal energy after performing the XOR operation with Thanos’ gauntlet power.

The key observation is that applying XOR with the same number twice brings the element back to its original value:

$a_i \oplus x\oplus x=a_i$

This means each stone’s energy can only take two possible forms — either it remains the same ($a_i$) or becomes $a_i \oplus x$ after one operation.

Our goal is to check if any two stones can be made equal after performing some number of operations (possibly zero). To do this efficiently, we use the following logic:

Case 1 — Already Equal: If there are already two stones with the same energy $(a_i == a_j)$, no operation is needed. The answer is $0$.

Case 2 — One Operation: If by XORing one stone’s energy ($a_i \oplus x$) we can match another stone’s energy, then one operation is enough. That is, if ($a_i \oplus x$) exists in the array, the answer is $1$.

Case 3 — Impossible: If neither of the above cases is true, then it is impossible to make any two stones equal. The answer is $-1$.

Setter's Code:

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

int main() {   
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) 
        cin >> a[i];

        unordered_map<int, int> freq;
        bool fnd = false, fnd1 = false;
        
        for (int val : a) 
        freq[val]++;

        // Case 0: Already have duplicates
        for (auto &p : freq) {
            if (p.second > 1) {
                fnd = true;
                break;
            }
        }

        if (fnd) {
            cout << 0 << "\n";
            continue;
        }

        // Case 1: One operation can make duplicates
        for (int val : a) {
            int target = val ^ x;
            if (freq.find(target) != freq.end()) {
                fnd1 = true;
                break;
            }
        }

        if (fnd1)
            cout << 1 << "\n";
        else
            cout << -1 << "\n";
    }
}

Tester's Code:

from collections import defaultdict

t = int(input())
for _ in range(t):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))

    freq = defaultdict(int)
    fnd = False
    fnd1 = False

    for val in a:
        freq[val] += 1

    # Case 0: Already have duplicates
    for p in freq.values():
        if p > 1:
            fnd = True
            break

    if fnd:
        print(0)
        continue

    # Case 1: One operation can make duplicates
    for val in a:
        target = val ^ x
        if target in freq:
            fnd1 = True
            break

    if fnd1:
        print(1)
    else:
        print(-1)