Skip to content

3158. Find the XOR of Numbers Which Appear Twice

Description

You are given an array nums, where each number in the array appears either once or twice.

Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice.

 

Example 1:

Input: nums = [1,2,1,3]

Output: 1

Explanation:

The only number that appears twice in nums is 1.

Example 2:

Input: nums = [1,2,3]

Output: 0

Explanation:

No number appears twice in nums.

Example 3:

Input: nums = [1,2,2,1]

Output: 3

Explanation:

Numbers 1 and 2 appeared twice. 1 XOR 2 == 3.

 

Constraints:

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50
  • Each number in nums appears either once or twice.

Solutions

Solution 1: Counting

Thinking

XOR the values that occur exactly twice. The domain is tiny, so a frequency table is enough.

Count in one pass and XOR keys whose frequency is \(2\). An empty list yields \(0\).

Counter plus reduce(xor, ...) solves it in linear time.

We define an array or hash table cnt to record the occurrence of each number.

Next, we traverse the array nums. When a number appears twice, we perform an XOR operation with the answer.

Finally, we return the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(M)\). Where \(n\) is the length of the array nums, and \(M\) is the maximum value in the array nums or the number of distinct numbers in the array nums.

1
2
3
4
class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return reduce(xor, [x for x, v in cnt.items() if v == 2], 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        int[] cnt = new int[51];
        int ans = 0;
        for (int x : nums) {
            if (++cnt[x] == 2) {
                ans ^= x;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int duplicateNumbersXOR(vector<int>& nums) {
        int cnt[51]{};
        int ans = 0;
        for (int x : nums) {
            if (++cnt[x] == 2) {
                ans ^= x;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func duplicateNumbersXOR(nums []int) (ans int) {
    cnt := [51]int{}
    for _, x := range nums {
        cnt[x]++
        if cnt[x] == 2 {
            ans ^= x
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function duplicateNumbersXOR(nums: number[]): number {
    const cnt: number[] = Array(51).fill(0);
    let ans: number = 0;
    for (const x of nums) {
        if (++cnt[x] === 2) {
            ans ^= x;
        }
    }
    return ans;
}

Solution 2: Bit Manipulation

Thinking

A hash map is unnecessary when every value is at most \(50\).

A 64-bit mask records whether a value has been seen; the second sighting XORs it into the answer.

If bit \(x\) of \(mask\) is set, XOR \(x\) into \(ans\); otherwise set the bit. Extra arrays disappear.

Since the given number range in the problem is \(1 \leq \textit{nums}[i] \leq 50\), we can use a \(64\)-bit integer to store the occurrence of each number.

We define an integer \(\textit{mask}\) to record whether each number has appeared.

Next, we traverse the array \(\textit{nums}\). When a number appears twice, i.e., the \(x\)-th bit in the binary representation of \(\textit{mask}\) is \(1\), we perform an XOR operation with the answer. Otherwise, we set the \(x\)-th bit of \(\textit{mask}\) to \(1\).

Finally, we return the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        ans = mask = 0
        for x in nums:
            if mask >> x & 1:
                ans ^= x
            else:
                mask |= 1 << x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        int ans = 0;
        long mask = 0;
        for (int x : nums) {
            if ((mask >> x & 1) == 1) {
                ans ^= x;
            } else {
                mask |= 1L << x;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int duplicateNumbersXOR(vector<int>& nums) {
        int ans = 0;
        long long mask = 0;
        for (int x : nums) {
            if (mask >> x & 1) {
                ans ^= x;
            } else {
                mask |= 1LL << x;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func duplicateNumbersXOR(nums []int) (ans int) {
    mask := 0
    for _, x := range nums {
        if mask>>x&1 == 1 {
            ans ^= x
        } else {
            mask |= 1 << x
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function duplicateNumbersXOR(nums: number[]): number {
    let ans = 0;
    let mask = 0n;
    for (const x of nums) {
        if ((mask >> BigInt(x)) & 1n) {
            ans ^= x;
        } else {
            mask |= 1n << BigInt(x);
        }
    }
    return ans;
}

Comments