Problem Statement
Given an array of integers nums, where every element appears three times except for one element that appears once, find that single element.
Examples
Example 1:
Input: nums = [2, 2, 3, 2]
Output: 3
Explanation: Every element except 3 appears three times.Example 2:
Input: nums = [0, 1, 0, 1, 0, 1, 2]
Output: 2
Explanation: Every element except 2 appears three times.Different Approaches
1️⃣ Brute Force (using Hashmap)
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 = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
| |
| |
| |
| |
| |
+----------+
Hashmap(number, frequency)First Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| |
| |
| (0, 1) |
+----------+
Hashmap(number, frequency)Second Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| |
| (1, 1) |
| (0, 1) |
+----------+
Hashmap(number, frequency)Third Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| |
| (1, 1) |
| (0, 2) |
+----------+
Hashmap(number, frequency)Fourth Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| |
| (1, 2) |
| (0, 2) |
+----------+
Hashmap(number, frequency)Fifth Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| |
| (1, 2) |
| (0, 3) |
+----------+
Hashmap(number, frequency)Sixth Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| |
| (1, 3) |
| (0, 3) |
+----------+
Hashmap(number, frequency)Seventh Iteration:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| (2, 1) |
| (1, 3) |
| (0, 3) |
+----------+
Hashmap(number, frequency)Loop Termination:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 0 | 1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
index 0 1 2 3 4 5 6
^
|
i
| |
| |
| (2, 1) |
| (1, 3) |
| (0, 3) |
+----------+
Hashmap(number, frequency)
Since i has exceeded the array bounds,
so loop will be terminated.
Now, we need to iterate over the map
to check the frequency of every element
return the element whose frequency
is 1.Iterate through the Hashmap:
Iteration 1:
| |
| |
| (2, 1) |
| (1, 3) |
->| (0, 3) |
+----------+
Hashmap(number, frequency)
Does frequency of 0 == 1
False
Iteration 2:
| |
| |
| (2, 1) |
->| (1, 3) |
| (0, 3) |
+----------+
Hashmap(number, frequency)
Does frequency of 1 == 1
False
Iteration 3:
| |
| |
->| (2, 1) |
| (1, 3) |
| (0, 3) |
+----------+
Hashmap(number, frequency)
Does frequency of 2 == 1
True
Thus we have the required number
which is 2.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 = {2, 2, 2, 3};
/* 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).
- Traversing the array to update the Hash Map -
- 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️⃣ Better Approach (count the bit at each position)
Intuition:
A better approach would be to use the properties of binary representation and bit manipulation. The idea is to count the bits at each position.
For elements appearing three times, the bit count will be a multiple of three. The unique element's bit will not follow this pattern, using which it could be identified.
Approach:
- Start by initializing a variable to store the result, which will eventually hold the unique element.
- Loop through each bit position (from 0 to 31, assuming 32-bit integers) to examine the contribution of each bit across all numbers in the array.
- For each bit position, count how many numbers in the array have a set bit (bit value of 1) at that specific position.
- For each bit position, if the count of set bits is not a multiple of three, it means the unique element has a set bit at that position.
- Update the result variable by setting the corresponding bit position where the count of set bits is not a multiple of three.
- After processing all bit positions, the result variable will contain the unique element that appears only once in the array.
Dry Run:
Initialization:
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
index 0 1 2 3
2 in binary: 00000000000000000000000000000010
3 in binary: 00000000000000000000000000000011We will get bit by bit of every element of the array (from Right to Left) (Least Significant Bit to Most Significant Bit)
Start from the LSB (bit at index 0):
For Bit 0
n = 4 (size of array)
ans = 0
Iterate through the array
Iteration 1:
i = 0
count = 0
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
index 0 1 2 3
^
|
i
nums[i] which is 2 (...0010)
Does the Bit 0 is 1
No
Don't change count
Iteration 2:
i = 1
count = 0
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
index 0 1 2 3
^
|
i
nums[i] which is 2 (...0010)
Does the Bit 0 is 1
No
Dont Change count
Iteration 3:
i = 2
count = 0
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
index 0 1 2 3
^
|
i
nums[i] which is 2 (...0010)
Does the Bit 0 is 1
No
Dont Change count
Iteration 4:
i = 3
count = 0
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
index 0 1 2 3
^
|
i
nums[i] which is 3 (...0011)
Does the Bit 0 is 1
Yes
Increment count
count is now 1.
Since i will exceed array bounds after it. So this loop
will terminate here.If the count is not multiple of 3, the corresponding bit is set in the ans:
If it's not a multiple of 3, it means this bit contributes to the unique number (since all the elements appearing three times would contribute 1s in multiples of 3 at each bit position).
ans = 0
Since count is 1, which is not multiple of 3
because count % 3
= 1 % 3
= 1
Set the corresponding bit (i.e Bit 0) in the ans
ans = ans | (1 << BitIndex), BitIndex is 0 here, which is LSB.Do this for Every Bit (i.e from 0 to 31)
It's like we are building the answer from bit by bit. At last we have the required number.
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){
// Variable to store size of array
int n = nums.size();
// Variable to store the ans
int ans = 0;
// Checking every bit position
for(int bitIndex = 0; bitIndex < 32; bitIndex++) {
/* Variable to count number of
set bits in bitIndex position */
int count = 0;
// Traversing all elements
for(int i = 0; i < n; i++) {
/* Counting elements having set
bits at bitIndex position */
if(nums[i] & (1 << bitIndex)) {
count++;
}
}
// Updating bits in answer
if(count % 3 != 0) {
ans |= (1 << bitIndex);
}
}
return ans;
}
};
int main() {
vector<int> nums = {2, 2, 2, 3};
/* 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(32*N)– For every 32-bit position, all the elements of the array are traversed. - Space Complexity:
O(1)– Using a couple of variables i.e., constant space.