# Single Number II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/single-number-ii)
Canonical: https://scaleengineer.com/dsa/problems/single-number-ii
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## 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 * 104`
* `-231 <= nums[i] <= 231 - 1`
* Each element in `nums` appears exactly **three times** except for one element which appears **once**.

# Approaches
## Hash Map Approach
This approach uses a hash map to store the frequency of each number in the array. We iterate through the array, populating the map. Then, we iterate through the map to find the number with a frequency of 1.
**Time:** O(n) · **Space:** O(n)
**Pros:** Simple to understand and implement.; Generalizable to other frequency-based problems.
**Cons:** Violates the problem's constraint of using only constant extra space.
### Explanation
The algorithm involves two main passes over the data. First, we iterate through the `nums` array to build a frequency map. For each number, we use it as a key and its frequency as the value. If the number is already in the map, we increment its value; otherwise, we add it with a value of 1. In the second pass, we iterate through the entries of the hash map. The entry whose value is 1 corresponds to the single number, and we return its key. This method is straightforward to implement and understand but does not meet the space complexity requirement of the problem.

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

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        // This line should not be reached given the problem constraints
        return -1;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` to store the frequency of each number.
- Iterate through the `nums` array. For each number `num`, increment its count in the map.
- After building the frequency map, iterate through its entries.
- Return the key for which the corresponding value (frequency) is 1.

## Bit Manipulation by Counting Set Bits
This approach leverages bitwise operations to solve the problem in linear time and constant space. The core idea is to count the occurrences of '1' for each bit position across all numbers. Since every number except one appears three times, the sum of bits at any position will be a multiple of 3, unless the single number has a '1' at that bit position.
**Time:** O(n) · **Space:** O(1)
**Pros:** Meets both linear time and constant space complexity requirements.; The logic can be generalized to find an element with a different frequency.
**Cons:** Less intuitive than the hash map approach for beginners.; The constant factor (32) makes it slightly slower in practice than the single-pass bit manipulation approach, although both are O(n).
### Explanation
We can determine the bits of the single number one by one. For each bit position from 0 to 31 (for a 32-bit integer), we calculate the sum of the bits of all numbers in the array at that specific position. Let's say for the `i`-th bit, the sum is `S`. If the `i`-th bit of the single number is 0, then all other numbers contribute to this sum. Since each of them appears three times, their `i`-th bits will be summed up in groups of three, making `S` a multiple of 3. However, if the `i`-th bit of the single number is 1, then `S` will be `(a multiple of 3) + 1`. Therefore, by checking `S % 3`, we can determine the `i`-th bit of the single number. We construct the final result by setting the bits accordingly.

```java
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        // Iterate over each bit position (0 to 31 for a 32-bit integer)
        for (int i = 0; i < 32; i++) {
            int sumOfBits = 0;
            // Calculate the sum of the i-th bit for all numbers
            for (int num : nums) {
                // Check if the i-th bit is set in the current number
                if (((num >> i) & 1) == 1) {
                    sumOfBits++;
                }
            }
            // If the sum is not a multiple of 3, the single number has a 1 at this bit position
            if (sumOfBits % 3 != 0) {
                // Set the i-th bit in the result
                result |= (1 << i);
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize a variable `result` to 0.
- Loop through each bit position `i` from 0 to 31.
- For each bit position, calculate the sum of the `i`-th bits of all numbers in the `nums` array.
- If the sum of bits for the `i`-th position is not a multiple of 3, it means the single number has a 1 at this bit position.
- Set the `i`-th bit in the `result` using a bitwise OR operation: `result |= (1 << i)`.
- After checking all 32 bits, `result` will hold the single number.

## Bit Manipulation with `ones` and `twos` (Finite Automata)
This is a highly efficient and clever bit manipulation approach that solves the problem in a single pass. It uses two integer variables, `ones` and `twos`, to simulate a state machine for each bit. The `ones` variable stores the bits that have appeared once (or 4, 7, ... times), and `twos` stores the bits that have appeared twice (or 5, 8, ... times). When a bit appears three times, it's cleared from both `ones` and `twos`.
**Time:** O(n) · **Space:** O(1)
**Pros:** Extremely efficient, with a smaller constant factor than the bit counting method as it's a single pass.; Satisfies all problem constraints (linear time, constant space).; An elegant and clever solution.
**Cons:** The logic behind the bitwise operations can be difficult to grasp without understanding the underlying state machine concept.
### Explanation
The idea is to track the count of '1's for each bit position modulo 3. We can represent these counts using two bits: `(twos, ones)`. The state transitions are as follows:
- `00` -> `01` (seen once)
- `01` -> `10` (seen twice)
- `10` -> `00` (seen three times, reset)
We iterate through the input array `nums`. For each number `num`, we update the `ones` and `twos` variables to reflect these state transitions for every bit. The update logic is:
- `ones = (ones ^ num) & ~twos;`
- `twos = (twos ^ num) & ~ones;`
For bits belonging to the single number, they will transition to state `01` and remain there. For bits belonging to numbers that appear three times, they will cycle through `01`, `10`, and back to `00`, effectively canceling themselves out. After processing all numbers, the `ones` variable will hold exactly the single number.

```java
class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0;
        int twos = 0;
        for (int num : nums) {
            // 'ones' holds the bits that have appeared 3k+1 times
            // 'twos' holds the bits that have appeared 3k+2 times
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}
```
### Algorithm
- Initialize two integer variables, `ones` and `twos`, to 0.
- Iterate through each `num` in the input array `nums`.
- In each iteration, update `ones` and `twos` using the following bitwise formulas:
  - `ones = (ones ^ num) & ~twos`
  - `twos = (twos ^ num) & ~ones`
- After the loop completes, the `ones` variable will contain the single number that appeared only once.
- Return `ones`.

# Solutions
### Java

```java
class Solution {
public
  int singleNumber(int[] nums) {
    int a = 0, b = 0;
    for (int c : nums) {
      int aa = (~a & b & c) | (a & ~b & ~c);
      int bb = ~a & (b ^ c);
      a = aa;
      b = bb;
    }
    return b;
  }
}

```

### JavaScript

```javascript
function singleNumber ( nums ) { 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 ; }
```

### CPP

```cpp
class Solution {
public:
  int singleNumber(vector<int> &nums) {
    int a = 0, b = 0;
    for (int c : nums) {
      int aa = (~a & b & c) | (a & ~b & ~c);
      int bb = ~a & (b ^ c);
      a = aa;
      b = bb;
    }
    return b;
  }
};

```

### Python

```python
''' A 32-bit number can be created to count the number of occurrences of 1 in each digit. If a certain digit is 1, then if the integer appears three times, the remainder of 3 is 0, so that the numbers of each digit position are added up then take the remainder of 3, and the final number remaining is a single number. ''' class Solution : def singleNumber ( self , nums : List [ int ]) -> int : ans = 0 for i in range ( 32 ): cnt = sum ( num >> i & 1 for num in nums ) if cnt % 3 : if i == 31 : # int overflow， or just throw exception ans -= 1 << i else : ans |= 1 << i return ans ############ class Solution : def singleNumber ( self , nums : List [ int ]) -> int : a = b = 0 for c in nums : aa = ( ~ a & b & c ) | ( a & ~ b & ~ c ) bb = ~ a & ( b ^ c ) a , b = aa , bb return b
```