137. Single Number II - Solution & Explanation

Q: Is Single Number II easy or hard?

Single Number II is rated Medium on LeetCode. The hash map solution is straightforward, but the expected optimal answer requires understanding bit manipulation and modular arithmetic.

Q: Single Number II Python/Java solution

In Python or Java, the typical implementation loops through 32 bit positions, counts set bits across the array, and reconstructs the answer using bit operations. The algorithm runs in O(n) time and uses constant space.

Q: How to solve Single Number II in O(n)?

Iterate over each bit position and count how many numbers in the array have that bit set. Since all repeating numbers appear three times, their contributions cancel when you compute count % 3. Reconstruct the single number from the remaining bits.

Q: What is the best approach for Single Number II?

The optimal approach uses bit manipulation with modulo arithmetic. Count how many numbers have each bit set from 0 to 31, then take the count modulo 3. Bits that remain correspond to the unique number. This runs in O(n) time and O(1) extra space.

Q: Is Single Number II asked at Google/Amazon/Meta?

Single Number II is a common bit manipulation interview problem and variations have appeared at companies like Amazon, Google, and Meta. It tests understanding of binary operations, modular arithmetic, and space optimization.

Q: What data structure is used in Single Number II?

Two common approaches exist. A hash map can store frequencies of each number, while the optimal solution avoids extra data structures by using bit manipulation and integer variables.

Q: What is the time complexity of Single Number II?

The optimal bit manipulation solution runs in O(n) time because the array is scanned while counting bits. Since there are only 32 bit positions for integers, the constant factor remains small. Space complexity is O(1).

The problem

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 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Approach overview

Problem Overview: You are given an integer array where every element appears exactly three times except for one element that appears once. The task is to find that single element. The challenge is doing it efficiently without extra memory while scanning the array only once.

Approach 1: Use a Map to Count Frequencies (O(n) time, O(n) space)

The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map using map[num]++. After building the frequency table, iterate through the map and return the number whose count equals 1. Hash lookups and insertions run in constant time on average, so the entire pass over the array costs O(n) time.

This method is easy to implement and works for any frequency-based variant of the problem. The downside is memory usage: the map may store up to n distinct elements, giving O(n) space complexity. In interviews, this approach demonstrates that you recognize the frequency pattern but it doesn't fully exploit the bit constraints of the problem. Problems involving counting or frequency tables commonly appear in array and hash-based questions.

Approach 2: Bit Manipulation (O(n) time, O(1) space)

The optimal approach analyzes the binary representation of every number. Since all numbers except one appear exactly three times, the sum of bits at each position must be a multiple of three for those repeated numbers. The unique number contributes the remaining bits. For each bit position from 0 to 31, iterate through the array and count how many numbers have that bit set.

Compute count % 3 for each bit position. If the remainder is 1, the unique number has that bit set. Reconstruct the answer by setting those bits in the result integer. This works because triples cancel out under modulo 3 arithmetic. The algorithm scans the array for each bit position, giving O(32 * n) time which simplifies to O(n). Only a few integer variables are used, so space complexity is O(1).

This technique is a classic example of counting bits with modular arithmetic and appears frequently in bit manipulation interview questions. It avoids auxiliary data structures and works even when the input size is large.

Recommended for interviews: The bit manipulation approach is the expected optimal solution. Interviewers want to see whether you recognize the pattern that repeated numbers cancel out when counted modulo three. Starting with the hash map solution shows clear thinking, but transitioning to the constant-space bit technique demonstrates stronger algorithmic skill and familiarity with low-level operations.

Approach 1: Bit Manipulation

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.

Python

def singleNumber(nums):
    ones, twos = 0, 0
    for num in nums:
        twos = twos | (ones & num)
        ones = ones ^ num
        common = ones & twos
        ones = ones & ~common
        twos = twos & ~common
    return ones

nums = [0, 1, 0, 1, 0, 1, 99]
print(singleNumber(nums))

Java

public class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            twos |= ones & num;
            ones ^= num;
            int common = ones & twos;
            ones &= ~common;
            twos &= ~common;
        }
        return ones;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 2};
        Solution sol = new Solution();
        System.out.println(sol.singleNumber(nums));
    }
}

C++

#include <vector>
using namespace std;

int singleNumber(vector<int>& nums) {
    int ones = 0, twos = 0, common = 0;
    for (int num : nums) {
        twos |= ones & num;
        ones ^= num;
        common = ones & twos;
        ones &= ~common;
        twos &= ~common;
    }
    return ones;
}

int main() {
    vector<int> nums = {0, 1, 0, 1, 0, 1, 99};
    return singleNumber(nums);
}

JavaScript

function singleNumber(nums) {
  let ones = 0, twos = 0;
  for (let num of nums) {
      twos |= ones & num;
      ones ^= num;
      let common = ones & twos;
      ones &= ~common;
      twos &= ~common;
  }
  return ones;
}

const nums = [0, 1, 0, 1, 0, 1, 99];
console.log(singleNumber(nums));

#include <stdio.h>

int singleNumber(int* nums, int numsSize) {
    int ones = 0, twos = 0, common;
    for (int i = 0; i < numsSize; i++) {
        twos |= ones & nums[i];
        ones ^= nums[i];
        common = ones & twos;
        ones &= ~common;
        twos &= ~common;
    }
    return ones;
}

int main() {
    int nums[] = {2, 2, 3, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", singleNumber(nums, size));
    return 0;
}

public class Solution {
    public int SingleNumber(int[] nums) {
        int ones = 0, twos = 0;
        foreach (int num in nums) {
            twos |= ones & num;
            ones ^= num;
            int common = ones & twos;
            ones &= ~common;
            twos &= ~common;
        }
        return ones;
    }

    public static void Main() {
        int[] nums = {2, 2, 3, 2};
        Solution sol = new Solution();
        Console.WriteLine(sol.SingleNumber(nums));
    }
}

In Python, the problem is addressed with the same principle: ones and twos track the appearance of bits, and compatibility is ensured through logical operations to simulate three-bit counters for each position in the binary representation of numbers.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Use a Map to Count Frequencies

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.

Python

def singleNumber(nums):
    count = {}
    for num in nums:
        if num in count:
            count[num] += 1
        else:
            count[num] = 1
    for num in count:
        if count[num] == 1:
            return num

nums = [0, 1, 0, 1, 0, 1, 99]
print(singleNumber(nums))

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 2};
        Solution sol = new Solution();
        System.out.println(sol.singleNumber(nums));
    }
}

C++

#include <vector>
#include <unordered_map>
using namespace std;

int singleNumber(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int num : nums) {
        count[num]++;
    }
    for (auto &pair : count) {
        if (pair.second == 1) {
            return pair.first;
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {0, 1, 0, 1, 0, 1, 99};
    return singleNumber(nums);
}

JavaScript

function singleNumber(nums) {
  const count = {};
  for (let num of nums) {
    count[num] = (count[num] || 0) + 1;
  }
  for (let key in count) {
    if (count[key] === 1) {
      return Number(key);
    }
  }
}

const nums = [0, 1, 0, 1, 0, 1, 99];
console.log(singleNumber(nums));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int singleNumber(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize; i += 3) {
        if (i == numsSize - 1 || nums[i] != nums[i + 1]) {
            return nums[i];
        }
    }
    return -1;
}

int main() {
    int nums[] = {2, 2, 3, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", singleNumber(nums, size));
    return 0;
}

using 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));
    }
}

In Python, counting each number's occurrence using a dictionary allows for quick checks for the frequency. This method's simplicity is offset by its unnecessary use of extra space, contrary to the problem's constraints.

Complexity

Time Complexity: O(n)
Space Complexity: O(n) - for keeping counts in a dictionary.

Try this approach in the editor

Approach 3: Bitwise Operation

We can enumerate each binary bit i, and for each binary bit, we calculate the sum of all numbers on that bit. If the sum of the numbers on that bit can be divided by 3, then the number that only appears once on that bit is 0, otherwise it is 1.

The time complexity is O(n times log M), where n and M are the length of the array and the range of elements in the array, respectively. The space complexity is O(1).

TypeScript

function singleNumber(nums: number[]): number {
    let ans = 0;
    for (let i = 0; i < 32; i++) {
        const count = nums.reduce((r, v) => r + ((v >> i) & 1), 0);
        ans |= (count % 3) << i;
    }
    return ans;
}

func singleNumber(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		cnt := int32(0)
		for _, num := range nums {
			cnt += int32(num) >> i & 1
		}
		cnt %= 3
		ans |= cnt << i
	}
	return int(ans)
}

Swift

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var a = nums.sorted()
        var n = a.count
        for i in stride(from: 0, through: n - 2, by: 3) {
            if a[i] != a[i + 1] {
                return a[i]
            }
        }
        return a[n - 1]
    }
}

Rust

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        for i in 0..32 {
            let count = nums.iter().map(|v| (v >> i) & 1).sum::<i32>();
            ans |= count % 3 << i;
        }
        ans
    }
}

Try this approach in the editor

Approach 4: Digital Circuit

We can use a more efficient method that uses digital circuits to simulate the above bitwise operation.

Each binary bit of an integer can only represent 2 states, 0 or 1. However, we need to represent the sum of the i-th bit of all integers traversed so far modulo 3. Therefore, we can use two integers a and b to represent it. There are three possible cases:

The i-th bit of integer a is 0 and the i-th bit of integer b is 0, which means the modulo 3 result is 0;
The i-th bit of integer a is 0 and the i-th bit of integer b is 1, which means the modulo 3 result is 1;
The i-th bit of integer a is 1 and the i-th bit of integer b is 0, which means the modulo 3 result is 2.

We use integer c to represent the number to be read in, and the truth table is as follows:

`a_i`	`b_i`	`c_i`	New `a_i`	New `b_i`
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	0	0

Based on the truth table, we can write the logical expression:

$a_i = a_i' b_i c_i + a_i b_i' c_i'

and:

b_i = a_i' b_i' c_i + a_i' b_i c_i' = a_i' (b_i \oplus c_i)

The final result is b, because when the binary bit of b is 1, it means that the number appears only once.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.

TypeScript

function singleNumber(nums: number[]): number {
    let a = 0;
    let b = 0;
    for (const c of nums) {
        const aa = (~a & b & c) | (a & ~b & ~c);
        const bb = ~a & (b ^ c);
        a = aa;
        b = bb;
    }
    return b;
}

func singleNumber(nums []int) int {
	a, b := 0, 0
	for _, c := range nums {
		aa := (^a & b & c) | (a & ^b & ^c)
		bb := ^a & (b ^ c)
		a, b = aa, bb
	}
	return b
}

Rust

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut a = 0;
        let mut b = 0;

        for c in nums {
            let aa = (!a & b & c) | (a & !b & !c);
            let bb = !a & (b ^ c);
            a = aa;
            b = bb;
        }

        return b;
    }
}

Try this approach in the editor

Approach 5: Set + Math

TypeScript

function singleNumber(nums: number[]): number {
    const sumOfUnique = [...new Set(nums)].reduce((a, b) => a + b, 0);
    const sum = nums.reduce((a, b) => a + b, 0);
    return (sumOfUnique * 3 - sum) / 2;
}

Try this approach in the editor

Approach 6: Bit Manipulation

TypeScript

function singleNumber(nums: number[]): number {
    let [ans, acc] = [0, 0];

    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }

    return ans;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Bit Manipulation	Time Complexity: O(n) Space Complexity: O(1)
Use a Map to Count Frequencies	Time Complexity: O(n) Space Complexity: O(n) - for keeping counts in a dictionary.
Bitwise Operation	–
Digital Circuit	–
Set + Math	–
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Hash Map Frequency Count	O(n)	O(n)	Good first approach in interviews or when memory constraints are not strict
Bit Manipulation (Bit Counting mod 3)	O(n)	O(1)	Optimal solution when constant extra space is required

Frequently asked questions

Is Single Number II easy or hard?

Single Number II is rated Medium on LeetCode. The hash map solution is straightforward, but the expected optimal answer requires understanding bit manipulation and modular arithmetic.

Single Number II Python/Java solution

In Python or Java, the typical implementation loops through 32 bit positions, counts set bits across the array, and reconstructs the answer using bit operations. The algorithm runs in O(n) time and uses constant space.

How to solve Single Number II in O(n)?

Iterate over each bit position and count how many numbers in the array have that bit set. Since all repeating numbers appear three times, their contributions cancel when you compute count % 3. Reconstruct the single number from the remaining bits.

What is the best approach for Single Number II?

The optimal approach uses bit manipulation with modulo arithmetic. Count how many numbers have each bit set from 0 to 31, then take the count modulo 3. Bits that remain correspond to the unique number. This runs in O(n) time and O(1) extra space.

Is Single Number II asked at Google/Amazon/Meta?

Single Number II is a common bit manipulation interview problem and variations have appeared at companies like Amazon, Google, and Meta. It tests understanding of binary operations, modular arithmetic, and space optimization.

What data structure is used in Single Number II?

Two common approaches exist. A hash map can store frequencies of each number, while the optimal solution avoids extra data structures by using bit manipulation and integer variables.

What is the time complexity of Single Number II?

The optimal bit manipulation solution runs in O(n) time because the array is scanned while counting bits. Since there are only 32 bit positions for integers, the constant factor remains small. Space complexity is O(1).

Single Number II solution and explanation

The problem

Approach overview

Approach 1: Bit Manipulation

Approach 2: Use a Map to Count Frequencies

Approach 3: Bitwise Operation

Approach 4: Digital Circuit

Approach 5: Set + Math

Approach 6: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Single Number II solution and explanation

The problem

Approach overview

Approach 1: Bit Manipulation

Approach 2: Use a Map to Count Frequencies

Approach 3: Bitwise Operation

Approach 4: Digital Circuit

Approach 5: Set + Math

Approach 6: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems