Given an integer array where every element appears exactly three times except for one element which appears exactly once, find and return that unique single element.
Example 1
Input: arr = [2, 2, 3, 2]
Output: 3
Explanation: 2 appears three times, while 3 appears only once.
Example 2
Input: arr = [0, 1, 0, 1, 0, 1, 99]
Output: 99
Explanation: 0 and 1 appear three times, while 99 is the only element that appears once.
Brute Force Approach
Since every value except one appears exactly three times, we can count the occurrence of each number.
A hash map stores every value with its frequency. After processing the complete array, the number whose frequency is 1 is the required single element.
This approach is straightforward, but it requires additional memory for the frequency map.
Algorithm
Create a frequency map to store each number and how many times it appears.
Traverse
arrand increase the frequency of every value encountered.After all frequencies are stored, traverse the entries in the map.
Find the number whose frequency is
1, because the problem guarantees exactly one such value.Return that number.
Dry Run
Single Number II Brute Force Appraoch Dry Run.png
Solution
// C++ program to find the single element using a Hash Map#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to find the single number using frequency counting int singleNumber(vector<int>& nums) { unordered_map<int, int> frequency; // Count the occurrences of each number for (int num : nums) { frequency[num]++; } // Find the number that appears exactly once for (auto pair : frequency) { if (pair.second == 1) { return pair.first; } } return -1; // Fallback if no single number exists }};int main() { Solution sol; vector<int> arr = {2, 2, 3, 2}; cout << "The single number is: " << sol.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 entries are checked once.
Space Complexity: O(N), because the hash map may store O(N) distinct values.
Optimal Approach
Consider each bit position independently.
If a number appears three times, every set bit in its binary representation also contributes exactly three times at the same bit position. Therefore, the total number of set bits contributed by all repeated values at any position is divisible by 3.
The only extra contribution comes from the number that appears once. So, for every bit position, if the total count of set bits leaves a remainder after division by 3, that bit must be set in the unique number.
By checking every bit position and rebuilding those remaining bits, we obtain the answer using constant extra space.
Algorithm
Initialize
result = 0to gradually reconstruct the single number.Check every bit position of the integer representation, typically positions
0through31for a signed 32-bit integer.For the current bit position, initialize
bitCount = 0.Traverse the array and increase
bitCountwhenever that bit is set in the current number.Compute
bitCount % 3. Contributions from numbers appearing three times disappear, while a remainder of1means that bit belongs to the unique number.If the remainder is non-zero, set that bit in
result. After all bit positions are processed, returnresult.
Dry Run
Single Number II Optimal ppraoch Dry Run.png
Solution
// C++ program to find the single element using Bit Counting#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to find the single number using the bit counting approach int singleNumber(vector<int>& nums) { int result = 0; // Iterate through all 32 bits of an integer for (int i = 0; i < 32; i++) { int sum = 0; // Count how many numbers have the i-th bit set for (int num : nums) { if ((num >> i) & 1) { sum++; } } // If the sum is not a multiple of 3, the unique number has this bit set if (sum % 3 != 0) { result = result | (1 << i); } } return result; }};int main() { Solution sol; vector<int> arr = {2, 2, 3, 2}; cout << "The single number is: " << sol.singleNumber(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(32 × N), because all N elements are checked for each of the 32 bit positions. Since 32 is constant for a fixed-width integer, this simplifies to O(N).
Space Complexity: O(1), because only a few variables are used regardless of the input size.
Interview follow-up Questions
XOR cancels pairs because x ^ x = 0, but a value appearing three times does not disappear: x ^ x ^ x = x. Therefore, the direct XOR technique from Single Number I does not work here.
Be the first to add a comment.