Find the XOR of Numbers Which Appear Twice solution and explanation
Google
5 more videos on this problem
3158. Find the XOR of Numbers Which Appear Twice | EASY | Map | Array | O(n) | LeetCodeLeet's Code · 3:02 · 420 views
Leetcode 3158 | Find the XOR of Numbers Which Appear Twice | Leetcode Biweekly Contest 131Road To FAANG · 5:55 · 362 views
LeetCode 3158 | Find the XOR of Numbers Which Appear Twice | Detailed Solution and ExplanationErDelhiBoy · 8:41 · 276 views
3158. Find the XOR of Numbers Which Appear Twice | LC Biweekly Contest 131 | HINDI | TUTORIAL - 51Coding Kart · 4:57 · 255 views
Find the XOR of Numbers Which Appear Twice || Leetcode 3158🚀✨Adarsh Dubey · 3:06 · 188 views
DECODEDSA#LEVELUP#CONTESTSOL#leetcode#challenge#3158. Find the XOR of Numbers Which Appear TwiceDecode · 3:27 · 28 views
The problem
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.
Approach overview
Problem Overview: You are given an integer array nums. Some values appear once while others appear exactly twice. The task is to compute the XOR of all numbers that appear exactly two times. If no number appears twice, the result is 0. The key idea is identifying duplicates efficiently and combining them using the XOR operation.
Approach 1: Hashmap-based Frequency Count (Time: O(n), Space: O(n))
Traverse the array and maintain a frequency map using a hash table. For every number in nums, increment its count in the map. After building the frequency table, iterate through the map entries and select values with frequency equal to 2. XOR these values together to produce the final result. Hash table lookups and updates run in constant time on average, so the total runtime is O(n). This method is straightforward and works for any integer range, making it a reliable baseline when solving problems involving counting with a hash table.
Approach 2: Boolean Array for Appearance Tracking (Time: O(n), Space: O(1))
If the value range is small (as in this problem where numbers are bounded), a fixed-size boolean array can replace the hash map. Create a boolean array where the index represents the number and the value indicates whether it has been seen before. Iterate through nums: if the number has not been seen, mark it as seen; if it has already been seen, XOR it into the answer because this is the second occurrence. This avoids maintaining full counts and reduces memory overhead. The algorithm still scans the array once, giving O(n) time complexity while the auxiliary array size remains constant.
The approach relies on properties of bit manipulation. XOR accumulates each duplicated value exactly once when the second appearance is detected. The boolean lookup replaces a hash lookup with a direct index operation.
Recommended for interviews: The boolean array solution is typically preferred because it runs in O(n) time with constant extra space and very simple logic. Interviewers often expect candidates to recognize that the value range allows array indexing instead of a hash map. Starting with the hashmap approach demonstrates understanding of counting problems on an array, then optimizing to constant space shows stronger problem‑solving skill.
Approach 1: Hashmap-based Frequency Count
This approach involves using a hashmap (or dictionary) to count the frequency of each element in the array. After computing the frequencies, iterate over this map to find numbers that appear exactly twice, and calculate their XOR. This approach is straightforward as it leverages hashmap operations to keep track of occurrences efficiently.
def xor_of_duplicate(nums):
frequency = {}
for num in nums:
frequency[num] = frequency.get(num, 0) + 1
result = 0
for num, count in frequency.items():
if count == 2:
result ^= num
return result
print(xor_of_duplicate([1, 2, 1, 3]))import java.util.HashMap;
public class Solution {
public static int xorOfDuplicate(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int result = 0;
for (int key : map.keySet()) {
if (map.get(key) == 2) {
result ^= key;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1, 3};
System.out.println(xorOfDuplicate(nums));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int xorOfDuplicate(vector<int>& nums) {
unordered_map<int, int> frequency;
for (int num : nums) {
frequency[num]++;
}
int result = 0;
for (auto& [num, count] : frequency) {
if (count == 2) {
result ^= num;
}
}
return result;
}
int main() {
vector<int> nums = {1, 2, 1, 3};
cout << xorOfDuplicate(nums) << endl;
return 0;
}function xorOfDuplicate(nums) {
const frequency = {};
nums.forEach(num => {
frequency[num] = (frequency[num] || 0) + 1;
});
let result = 0;
for (let num in frequency) {
if (frequency[num] === 2) {
result ^= Number(num);
}
}
return result;
}
console.log(xorOfDuplicate([1, 2, 1, 3]));#include <stdio.h>
#include <string.h>
int xorOfDuplicate(int* nums, int numsSize) {
int hash[51] = {0};
for (int i = 0; i < numsSize; i++) {
hash[nums[i]]++;
}
int result = 0;
for (int i = 0; i < 51; i++) {
if (hash[i] == 2) {
result ^= i;
}
}
return result;
}
int main() {
int nums[] = {1, 2, 1, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", xorOfDuplicate(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public static int XorOfDuplicate(int[] nums) {
Dictionary<int, int> frequency = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
if (!frequency.ContainsKey(nums[i])) {
frequency[nums[i]] = 0;
}
frequency[nums[i]]++;
}
int result = 0;
foreach (var pair in frequency) {
if (pair.Value == 2) {
result ^= pair.Key;
}
}
return result;
}
public static void Main() {
int[] nums = { 1, 2, 1, 3 };
Console.WriteLine(XorOfDuplicate(nums));
}
}A dictionary stores the count of each number in the input list. Using dictionary methods such as get, frequencies are calculated. The second loop checks for numbers with a frequency of two, applying XOR to these numbers, and yields the result.
Time Complexity: O(n), reflecting the list traversal and dictionary operations.
Space Complexity: O(n), accounting for dictionary storage requirements.
Approach 2: Boolean Array for Appearance Tracking
This method employs a fixed-size boolean array to monitor whether a number has appeared once or twice. This array can be used to mark numbers as they are encountered and again to verify duplicates, applying an XOR operation once any number is confirmed to appear twice.
def xor_of_duplicate(nums):
appeared = [False] * 51
result = 0
for num in nums:
if appeared[num]:
result ^= num
appeared[num] = True
return result
print(xor_of_duplicate([1, 2, 1, 3]))public class Solution {
public static int xorOfDuplicate(int[] nums) {
boolean[] appeared = new boolean[51];
int result = 0;
for (int num : nums) {
if (appeared[num]) {
result ^= num;
}
appeared[num] = true;
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1, 3};
System.out.println(xorOfDuplicate(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int xorOfDuplicate(vector<int>& nums) {
vector<bool> appeared(51, false);
int result = 0;
for (int num : nums) {
if (appeared[num]) {
result ^= num;
}
appeared[num] = true;
}
return result;
}
int main() {
vector<int> nums = {1, 2, 1, 3};
cout << xorOfDuplicate(nums) << endl;
return 0;
}function xorOfDuplicate(nums) {
const appeared = new Array(51).fill(false);
let result = 0;
nums.forEach(num => {
if (appeared[num]) {
result ^= num;
}
appeared[num] = true;
});
return result;
}
console.log(xorOfDuplicate([1, 2, 1, 3]));#include <stdio.h>
#include <stdbool.h>
int xorOfDuplicate(int* nums, int numsSize) {
bool first_appearance[51] = {0};
int result = 0;
for (int i = 0; i < numsSize; i++) {
if (first_appearance[nums[i]]) {
result ^= nums[i];
}
first_appearance[nums[i]] = true;
}
return result;
}
int main() {
int nums[] = {1, 2, 1, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", xorOfDuplicate(nums, size));
return 0;
}using System;
public class Solution {
public static int XorOfDuplicate(int[] nums) {
bool[] appeared = new bool[51];
int result = 0;
foreach (int num in nums) {
if (appeared[num]) {
result ^= num;
}
appeared[num] = true;
}
return result;
}
public static void Main() {
int[] nums = { 1, 2, 1, 3 };
Console.WriteLine(XorOfDuplicate(nums));
}
}The use of a boolean list directly correlates to individual appearances. Marking numbers upon detection facilitates the identification of duplicates, executing their XOR for the intended solution.
Time Complexity: O(n), reflecting the pass required over each list element.
Space Complexity: O(1), indicating a constant memory footprint for the boolean tracking array.
Approach 3: 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.
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;
}func duplicateNumbersXOR(nums []int) (ans int) {
cnt := [51]int{}
for _, x := range nums {
cnt[x]++
if cnt[x] == 2 {
ans ^= x
}
}
return
}Approach 4: Bit Manipulation
Since the given number range in the problem is 1 leq nums[i] leq 50, we can use a 64-bit integer to store the occurrence of each number.
We define an integer mask to record whether each number has appeared.
Next, we traverse the array nums. When a number appears twice, i.e., the x-th bit in the binary representation of mask is 1, we perform an XOR operation with the answer. Otherwise, we set the x-th bit of mask to 1.
Finally, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
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;
}func duplicateNumbersXOR(nums []int) (ans int) {
mask := 0
for _, x := range nums {
if mask>>x&1 == 1 {
ans ^= x
} else {
mask |= 1 << x
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Hashmap-based Frequency Count | Time Complexity: O(n), reflecting the list traversal and dictionary operations. |
| Boolean Array for Appearance Tracking | Time Complexity: O(n), reflecting the pass required over each list element. |
| Counting | – |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashmap-based Frequency Count | O(n) | O(n) | General case when the value range is large or unknown |
| Boolean Array for Appearance Tracking | O(n) | O(1) | Best when numbers fall within a small fixed range and direct indexing is possible |
Frequently asked questions
Is Find the XOR of Numbers Which Appear Twice easy or hard?
The problem is classified as Easy because it relies on basic array traversal, duplicate detection, and the XOR operator. Once you recognize that the result should include only numbers that appear exactly twice, the implementation becomes straightforward.
Find the XOR of Numbers Which Appear Twice Python/Java solution
In Python or Java, iterate through the array while storing seen values in a set or boolean array. When a value appears for the second time, XOR it with the result variable. This implementation runs in O(n) time and requires minimal extra code.
How to solve Find the XOR of Numbers Which Appear Twice in O(n)?
Iterate through the array while tracking whether each number has appeared before. With a boolean array or hash set, detect the second occurrence and XOR the value into the result. Each element is processed once, producing an O(n) time algorithm.
What is the best approach for Find the XOR of Numbers Which Appear Twice?
The most efficient approach uses a boolean array to track whether a number has been seen before. When the same number appears the second time, XOR it with the running result. This processes the array in O(n) time and uses constant extra space because the tracking array size is fixed.
Is Find the XOR of Numbers Which Appear Twice asked at Google/Amazon/Meta?
Problems involving duplicate detection, XOR operations, and hash table counting appear frequently in coding interviews at companies like Amazon, Google, and Meta. This problem tests understanding of arrays, hash maps, and basic bit manipulation patterns.
What data structure is used in Find the XOR of Numbers Which Appear Twice?
The common data structures are a hash map for frequency counting or a boolean array for appearance tracking. The boolean array approach is more memory efficient when the input values fall within a small known range.
What is the time complexity of Find the XOR of Numbers Which Appear Twice?
Both common solutions run in O(n) time because the array is scanned once. A hash map frequency count uses O(n) space, while a boolean tracking array reduces space to O(1) when the value range is bounded.