Find the XOR of Numbers Which Appear Twice — Editorial

Opening the reading…

Intuitionwhy frequency two must be identified before applying XOR

The result is not the XOR of all array elements. A number that appears once must contribute nothing, while a number that appears twice must contribute once. Since the values are limited to 1 through 50, you can record how many times each possible value occurs and later select only the entries with frequency two.

After counting, scan the possible values rather than the original array. For every value counted twice, XOR it into the answer exactly once. XOR combines selected values without caring about their order, and the initial answer of zero naturally remains correct when no value has frequency two.

Approach

Create a frequency array with 51 positions, because value x belongs at index x and the largest possible value is 50; this avoids an unnecessary map and gives every possible value a direct slot.

Scan nums and increment freq[x] for every x; without this first pass, you cannot distinguish a value that appears once from one that appears twice.

Start ans at 0, the identity value for XOR, so values found later can be combined without a special first-element case.

Scan i from 1 through 50 and check freq[i] == 2; checking the complete value range ensures that every duplicated value is considered even if its occurrences were far apart in nums.

When freq[i] is exactly 2, XOR i into ans once; using the value-range scan prevents the same duplicate from being XORed twice just because it appeared twice in the input.

Return ans after the scan; if no frequency equals two, no XOR operation changes zero, which is exactly the required result.

Complexitythe value range is fixed by the problem

MEASURE	BOUND	WHY
Time	O(n + 50), which is O(n) because n >= 1	The first pass examines each of the n input elements once, and the second pass examines exactly 50 possible values. The two passes do not repeat input work, so their costs add rather than multiply.
Space	O(1) extra space	The frequency array always has 51 integer slots, independent of n. The returned integer is required output and is excluded from the working-space bound; there is no larger worst-case shape because the value range is fixed.

Here n is the length of nums; the possible value range has the fixed 51 slots for values 0 through 50.

Annotated solutionC++ · two passes · count first, XOR selected values once

CPPCount every value, then XOR each value whose frequency is exactly two.

#include <vector>
using namespace std;

class Solution {
public:
    int duplicateNumbersXOR(vector<int>& nums) {
        int freq[51] = {0};

        for (int x : nums) {
            freq[x]++;
        }

        int ans = 0;
        for (int i = 1; i <= 50; i++) {
            if (freq[i] == 2) {
                ans ^= i;
            }
        }

        return ans;
    }
};

The important placement is the second loop: it visits each possible value once, not each occurrence in nums. If value 1 appears twice, the loop still executes ans ^= 1 only once. That is what makes the contribution of a duplicate different from the contribution of a value that merely appears in the input.

The one-pass alternativea different arrangement, not an asymptotic optimisation

Because the statement guarantees that a value appears at most twice, you can process nums once. The first occurrence marks the value as seen; the second occurrence XORs it into the answer. This works only because a third occurrence is impossible. It uses the same fixed amount of extra storage and removes the separate scan over values, but the two-pass version makes the exact-frequency condition more explicit.

CPPMark the first occurrence and XOR the value when its second occurrence arrives.

#include <vector>
using namespace std;

class Solution {
public:
    int duplicateNumbersXOR(vector<int>& nums) {
        bool seen[51] = {false};
        int ans = 0;

        for (int x : nums) {
            if (seen[x]) {
                ans ^= x;
            } else {
                seen[x] = true;
            }
        }

        return ans;
    }
};