Problem Statement
Given an array of integers where every element appears twice except for one element which appears once, find that single element.
Examples
Example 1:
Input: arr = [2, 2, 1]
Output: 1
Explanation: Every element appears twice except for 1, which appears once.Example 2:
Input: arr = [4, 1, 2, 1, 2]
Output: 4
Explanation: Every element appears twice except for 4, which appears once.Example 3:
Input: arr = [1]
Output: 1
Explanation: The only element in the array is 1.Different Approaches
1️⃣ Using Hashmap (Brute Force) Approach
Intuition:
The brute force way to solve this will be to utilize a frequency counting approach. By keeping track of the frequency of each element in the array, the element that appears only once can be easily identified.
Approach:
- Use a hash map to store the frequency of each element in the array. The keys of the map are the elements of the array, and the values are their corresponding frequencies.
- Traverse the entire array once, and for each element, update its frequency count in the map.
- After populating the map with frequency counts, iterate over the map to find the element with a frequency of 1. This element is the unique integer that appears only once in the array.
- Return the unique element found in the map. If no such element exists (though the problem guarantees that one does), return -1.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
| |
| |
| |
| |
| |
| |
+--------+
HashMap (number, frequency)First Iteration:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
| |
| |
| |
| |
| |
| (1, 1) |
+--------+
HashMap (number, frequency)Second Iteration:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
| |
| |
| |
| |
| (2, 1) |
| (1, 1) |
+--------+
HashMap (number, frequency)Third Iteration:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
| |
| |
| |
| |
| (2, 2) |
| (1, 1) |
+--------+
HashMap (number, frequency)Fourth Iteration:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
| |
| |
| |
| (3, 1) |
| (2, 2) |
| (1, 1) |
+--------+
HashMap (number, frequency)Fifth Iteration:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
| |
| |
| |
| (3, 1) |
| (2, 2) |
| (1, 2) |
+--------+
HashMap (number, frequency)Loop Termination:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
0 1 2 3 4
^
|
i
| |
| |
| |
| (3, 1) |
| (2, 2) |
| (1, 2) |
+--------+
HashMap (number, frequency)
Since i has exceeded the array bounds, the loop
will terminate here.
Now iterate over the map to find the element with a frequency of 1. This element is the unique integer that appears only once in the array.Iterating Over the HashMap
First Iteration:
| |
| (3, 1) |
| (2, 2) |
->| (1, 2) |
+--------+
HashMap (number, frequency)
frequency = 2
Second Iteration:
| |
| (3, 1) |
->| (2, 2) |
| (1, 2) |
+--------+
HashMap (number, frequency)
frequency = 2
Third Iteration:
| |
->| (3, 1) |
| (2, 2) |
| (1, 2) |
+--------+
HashMap (number, frequency)
frequency = 1
This is the required number, return it.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the single
number in the given array */
int singleNumber(vector<int>& nums){
/* Map to store the elements
and their frequencies */
unordered_map <int, int> mpp;
// Iterate on the array
for(int i=0; i < nums.size(); i++) {
mpp[nums[i]]++; //Update the map
}
//Iterate on the map
for(auto it : mpp) {
// If frequency is 1
if(it.second == 1) {
// Return the element
return it.first;
}
}
/* Return -1, if there is no
number having frequency 1 */
return -1;
}
};
int main() {
vector<int> nums = {1, 2, 2, 4, 3, 1, 4};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the single
number in the given array */
int ans = sol.singleNumber(nums);
cout << "The single number in given array is: " << ans;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N)(whereNis the size of the array) –- Traversing the array to update the Hash Map - O(N).
- Traversing on the map - O(N) (in worst case).
- Space Complexity:
O(N)– Using a hashmap data structure and in the worst-case (when all elements in the array are unique), it will store N key-value pairs.
2️⃣ Optimal Approach (using XOR Operator)
This problem can be efficiently solved using bit manipulation. The key insight is that XOR (^) has some special properties that make it perfect for this problem:
x ^ x = 0(XOR-ing the same number results in 0).x ^ 0 = x(XOR-ing a number with 0 results in the number itself).- XOR is commutative and associative, which means the order of operations doesn’t matter.
Using these properties, we can XOR all the numbers in the array. Since every number except one appears twice, XOR-ing all the elements will cancel out the numbers that appear twice, leaving only the single number.
Approach:
- XOR all elements in the array.
- The duplicate numbers will cancel out (because
x ^ x = 0), and the result will be the single number.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
XOR = 0First Iteration:
XOR = 0
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
^
|
i
XOR = XOR ^ nums[i]
= 0 ^ 1
= 1Second Iteration:
XOR = 1
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
^
|
i
XOR = XOR ^ nums[i]
= 1 ^ 2
= 3Third Iteration:
XOR = 3
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
^
|
i
XOR = XOR ^ nums[i]
= 3 ^ 2
= 1Fourth Iteration:
XOR = 1
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
^
|
i
XOR = XOR ^ nums[i]
= 1 ^ 3
= 2Fifth Iteration:
XOR = 2
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
^
|
i
XOR = XOR ^ nums[i]
= 2 ^ 1
= 3Loop Termination:
XOR = 3
+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 3 | 1 |
+-----+-----+-----+-----+-----+
index 0 1 2 3 4
^
|
i
Since i has exceeded the bounds of the array,
the loop will terminate here, and
XOR contains the unique elements which we
needed. All we need is to return it.Code:
#include <iostream>
#include <vector>
using namespace std;
// Function to find the single number using XOR
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num; // XOR all elements
}
return result;
}
int main() {
vector<int> arr = {4, 1, 2, 1, 2};
cout << "The single number is: " << singleNumber(arr) << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(n), wherenis the number of elements in the array. We traverse the array once and perform constant time XOR operations. - Space Complexity:
O(1), since we only use a single variable (result) to store the XOR result.