Given an array of integers where every element appears exactly twice except for one element which appears exactly once, find and return that unique element.
Example 1
Input: arr = [2, 2, 1]
Output: 1
Explanation: 2 appears twice, while 1 appears only once.
Example 2
Input: arr = [4, 1, 2, 1, 2]
Output: 4
Explanation: 1 and 2 appear twice, while 4 is the only element that appears once.
Brute Force Approach
Since every value except one appears exactly twice, we can count how many times each number occurs.
A hash map stores each number along with its frequency. After processing the array, the number whose frequency is 1 is the unique element.
This approach is straightforward, but the frequency map requires additional space proportional to the number of distinct values.
Algorithm
Create a frequency map to store each array value and the number of times it appears.
Traverse
arrand increase the frequency of every element encountered.After all frequencies are stored, traverse the frequency map.
Find the value whose frequency is
1, because the problem guarantees exactly one such element.Return that value as the unique number.
Dry Run
Single Number I Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int singleNumber(vector<int>& arr) { /* * Store how many times each value appears so the * element with frequency 1 can be identified later. */ unordered_map<int, int> frequency; for (int num : arr) { frequency[num]++; } for (auto& entry : frequency) { if (entry.second == 1) { return entry.first; } } return -1; }};int main() { vector<int> arr = {4, 1, 2, 1, 2}; Solution solution; cout << solution.singleNumber(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(N) on average, because the array is traversed once to build the hash map and the stored keys are then checked once.
Space Complexity: O(N), because the hash map may store up to O(N) distinct values.
Optimal Approach
The XOR operator has two useful properties:
x ^ x = 0
x ^ 0 = x
Since every repeated number appears exactly twice, XORing all array elements causes every duplicate pair to cancel out.
Because XOR is also commutative and associative, the duplicate values do not need to appear next to each other. After all pairs cancel, only the number that appears once remains.
This gives the same O(N) time complexity as frequency counting while removing the extra hash-map space.
Algorithm
Initialize
result = 0, because XORing any value with0keeps the value unchanged.Traverse every element
numin the array.Update
resultusingresult ^ numso the current value becomes part of the cumulative XOR.Duplicate values eventually cancel because
x ^ x = 0, regardless of their positions in the array.After the traversal finishes, return
result, which contains the only value that appeared once.
Dry Run
Single Number I Optimal Approach Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int singleNumber(vector<int>& arr) { /* * Starting with 0 keeps the first value unchanged * because 0 ^ x = x. */ int result = 0; /* * Equal values cancel under XOR, so every repeated * pair disappears from the cumulative result. */ for (int num : arr) { result ^= num; } /* * All duplicated values have canceled, * leaving only the value that appeared once. */ return result; }};int main() { vector<int> arr = {4, 1, 2, 1, 2}; Solution solution; cout << solution.singleNumber(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because every array element is processed exactly once.
Space Complexity: O(1), because only one variable is used to store the cumulative XOR.
FAQs
Q1. Why does XOR remove numbers that appear twice?
For any integer x, x ^ x = 0. Therefore, every duplicated value cancels itself when all array elements are XORed together.
Q2. Does the order of the array matter for the XOR approach?
No. XOR is commutative and associative, so the elements can appear in any order and duplicate values will still cancel.
Q3. Why is result initialized to 0?
Because 0 ^ x = x. Starting with 0 allows the first array value to enter the cumulative XOR without changing it.
Q4. Why is the XOR approach better than using a hash map?
Both approaches take O(N) time, but the hash-map approach requires O(N) additional space, while XOR uses only O(1) auxiliary space.
Q5. What happens if more than one number appears only once?
This approach no longer directly gives one of those values. Their XOR would remain in the final result, so a different technique is needed for variants containing multiple unique elements.
Q6. Would this approach work if the repeated elements appeared three times instead of twice?
No. The cancellation x ^ x = 0 specifically handles pairs. If every repeated value appears three times, a different bit-counting technique is required.
Be the first to add a comment.