Find the XOR of Numbers Which Appear Twice
EasyPrompt
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 <= 501 <= nums[i] <= 50- Each number in
numsappears either once or twice.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by using a HashSet to keep track of numbers encountered so far. This allows us to find duplicates in a single pass through the array, leading to a linear time complexity.
Algorithm
- Initialize a result variable
xorResultto 0. - Initialize a
HashSetcalledseento store numbers encountered so far. - Iterate through each number
numin thenumsarray. - For each
num, attempt to add it to theseenset. - The
addmethod of aHashSetreturnsfalseif the element is already present. - If
seen.add(num)returnsfalse, it signifies a duplicate. XOR thisnumwithxorResult. - If it returns
true, it's the first occurrence of the number, so we do nothing. - After the loop, return
xorResult.
Walkthrough
We initialize a result variable xorResult to 0 and a HashSet called seen. We then iterate through each number num in the nums array. For each num, we check if it's already in the seen set. A neat trick is to use the boolean return value of seen.add(num). If the number is already present, add returns false, and we know it's a duplicate. In this case, we XOR the number with our xorResult. If the number is not present, add returns true, and we simply move on. After iterating through all the numbers, xorResult will contain the final XOR sum of all duplicate numbers.
import java.util.HashSet;import java.util.Set; class Solution { public int duplicateNumbersXOR(int[] nums) { int xorResult = 0; Set<Integer> seen = new HashSet<>(); for (int num : nums) { // If the number is already in the set, it's a duplicate. if (!seen.add(num)) { xorResult ^= num; } } return xorResult; }}Complexity
Time
O(n), where n is the length of the `nums` array. We iterate through the array once, and set operations (add, contains) take O(1) average time.
Space
O(k), where k is the number of unique elements in the array. In the worst case, all elements are unique, leading to O(n) space.
Trade-offs
Pros
Efficient O(n) time complexity.
Conceptually simple and easy to implement.
Cons
Requires extra space for the set, which can be O(n) in the worst case (when all elements are unique).
This approach uses a straightforward, brute-force method to find duplicate numbers. It involves iterating through the array with two nested loops to compare every element with every other element that comes after it. A set is used to keep track of duplicates that have already been accounted for to prevent them from being XORed multiple times.
Algorithm
- Initialize a result variable
xorResultto 0. - Initialize a
HashSetcalledprocessedDuplicatesto store numbers that have already been identified as duplicates. - Use a nested loop to compare every element with every other element.
- The outer loop runs from
i = 0ton-1. - The inner loop runs from
j = i + 1ton-1.
- The outer loop runs from
- If
nums[i]equalsnums[j]andnums[i]is not in theprocessedDuplicatesset:- It means we've found a new duplicate pair.
- XOR
nums[i]withxorResult. - Add
nums[i]to theprocessedDuplicatesset to avoid XORing it again.
- After the loops complete, return
xorResult.
Walkthrough
We initialize a result variable xorResult to 0 and a HashSet called processedDuplicates. The outer loop iterates from the first element to the second-to-last element (i), and the inner loop iterates from the element after i to the last element (j). Inside the inner loop, we check if nums[i] is equal to nums[j]. If they are equal and nums[i] has not been processed yet (i.e., not in processedDuplicates), we perform a bitwise XOR operation on xorResult with nums[i] and add nums[i] to the processedDuplicates set. After the loops complete, xorResult holds the bitwise XOR of all numbers that appear twice.
import java.util.HashSet;import java.util.Set; class Solution { public int duplicateNumbersXOR(int[] nums) { int xorResult = 0; Set<Integer> processedDuplicates = new HashSet<>(); for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { if (!processedDuplicates.contains(nums[i])) { xorResult ^= nums[i]; processedDuplicates.add(nums[i]); } } } } return xorResult; }}Complexity
Time
O(n^2), where n is the length of the `nums` array. The nested loops result in a quadratic runtime as each element is compared with every other element.
Space
O(k), where k is the number of unique duplicate numbers. In the worst case, k can be up to n/2, making the space complexity O(n).
Trade-offs
Pros
Simple to understand and implement without complex data structures.
Cons
Highly inefficient for larger arrays due to its quadratic time complexity.
Requires extra space to keep track of processed duplicates.
This is the most efficient approach, leveraging the problem's constraints. Since the numbers in the array are small and within a fixed range (1 to 50), we can use a simple array as a frequency counter. This avoids the overhead of hashing and provides constant space complexity.
Algorithm
- Leverage the constraint that
1 <= nums[i] <= 50. - Create an integer array
countsof size 51, initialized to zeros, to act as a frequency map. - Iterate through the input array
nums. For eachnum, increment the count at the corresponding index:counts[num]++. - Initialize a result variable
xorResultto 0. - Iterate through the
countsarray from index 1 to 50. - If
counts[i]is equal to 2, it means the numberiappeared twice. XORiwithxorResult. - Return
xorResult.
Walkthrough
This method takes advantage of the constraint that 1 <= nums[i] <= 50. We first create a frequency array, counts, of size 51 (for indices 0 to 50), initialized to all zeros. We iterate through the input array nums, and for each number num, we increment the count at its corresponding index in the counts array. After populating the frequency map, we initialize a result variable xorResult to 0. We then iterate through the counts array from 1 to 50. If the count for any number i is exactly 2, we XOR i with xorResult. Finally, we return the xorResult.
class Solution { public int duplicateNumbersXOR(int[] nums) { // Constraints: 1 <= nums[i] <= 50 int[] counts = new int[51]; for (int num : nums) { counts[num]++; } int xorResult = 0; for (int i = 1; i < counts.length; i++) { if (counts[i] == 2) { xorResult ^= i; } } return xorResult; }}Complexity
Time
O(n + m), where n is the length of `nums` and m is the range of possible values (50). Since m is a constant, the complexity simplifies to O(n).
Space
O(1). Since the range of numbers is fixed and small (1 to 50), the size of the `counts` array is constant (51) regardless of the input array's size.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal constant space complexity, O(1), due to the fixed-size array.
Very fast in practice due to direct array access instead of hashing.
Cons
This approach is only optimal because of the specific constraints on the values in
nums. It would be less memory-efficient if the numbers could be very large.
Solutions
Solution
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; }}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; }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.