Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Constraints:
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums appears exactly three times except for one element which appears once.The key idea in Single Number II is that every element appears exactly three times except one element that appears only once. A straightforward approach is to count the frequency of each number using a hash map, but this uses extra space. Interviewers typically expect a more optimized bit manipulation solution.
A common strategy is to analyze each bit position (0–31). By counting how many numbers have a set bit at a given position and taking the result mod 3, we can determine whether the unique number contributes to that bit. Reconstructing the number from these remaining bits yields the answer.
An even more elegant approach uses two bitmasks to simulate counting bits modulo three. These masks track which bits have appeared once and twice, automatically clearing bits that appear a third time. This allows processing the array in a single pass with constant extra space.
The optimal solutions run in O(n) time while maintaining O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Frequency Count | O(n) | O(n) |
| Bit Counting / Bitmask (mod 3) | O(n) | O(1) |
NeetCode
This approach uses bit manipulation to solve the problem with constant space and linear runtime. The idea is to count the number of times each bit is set in the given numbers modulo 3 using two integers. This effectively filters out the bits that appear in numbers repeated thrice and leaves the bits of the unique number.
Time Complexity: O(n) - where n is the number of elements in the array.
Space Complexity: O(1) - as only a fixed amount of space is used regardless of the input size.
1public class Solution {
2 public int SingleNumber(int[] nums) {
3 int ones = 0, twos = 0;
4 foreach (int num in nums) {
5 twos |= ones & num;
6 ones ^= num;
7 int common = ones & twos;
8 ones &= ~common;
9 twos &= ~common;
10 }
11 return ones;
12 }
13
14 public static void Main() {
int[] nums = {2, 2, 3, 2};
Solution sol = new Solution();
Console.WriteLine(sol.SingleNumber(nums));
}
}This C# solution is structurally similar to C++. Using time-efficient bit manipulation techniques, the algorithm maintains performance and clarity, employing logical operations to retain results of bits appearing less frequently than thrice.
This approach involves using a data structure to count occurrences of each number. Although this uses linear time complexity, it requires additional memory to store frequencies, which violates the constant space constraint.
Time Complexity: O(n log n) - primarily due to the sorting step.
Space Complexity: O(1) - if in-place sort is assumed.
1using System;
using System.Collections.Generic;
public class Solution {
public int SingleNumber(int[] nums) {
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (int num in nums) {
if (count.ContainsKey(num)) {
count[num]++;
} else {
count[num] = 1;
}
}
foreach (var kvp in count) {
if (kvp.Value == 1) {
return kvp.Key;
}
}
return -1;
}
public static void Main() {
int[] nums = {2, 2, 3, 2};
Solution sol = new Solution();
Console.WriteLine(sol.SingleNumber(nums));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of Single Number problems frequently appear in technical interviews at companies like Google, Amazon, and Meta. They test understanding of bit manipulation, optimization, and space-efficient algorithms.
Bit manipulation helps track how many times each bit appears across all numbers. Since most elements appear three times, taking the bit count modulo three isolates the contribution from the unique element.
The optimal approach uses bit manipulation. By counting the number of set bits at each position and taking the count modulo three, we can reconstruct the unique number. This achieves O(n) time with O(1) extra space.
A hash map can be used to count the frequency of each number and identify the one that appears once. While simple to implement, it requires O(n) extra space compared to the optimized bit manipulation approach.
This C# solution takes a dictionary approach to count and evaluate numbers. Despite its readability, it is not as efficient regarding space as required by the problem due to the extra storage needed for the frequency counts.