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

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

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