# Single Number II

## Single Number II

[原题链接](https://leetcode.com/problems/single-number-ii/)

### 描述

Given a **non-empty** array of integers, every element appears *three* times except for one, which appears exactly once. Find that single one.

**Note:**

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

### 例子

> Input: \[2,2,3,2] 
>
> Output: 3

### 解法一

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> seen;
        for(int i=0; i<nums.size(); i++){
            seen[nums[i]]++;
        }
        for(auto s:seen){
            if(s.second==1) return s.first;
        }
        return 0;
    }
};
```

### 解法 Binary

Consider the following fact:

Write all numbers in binary form, then for any bit 1 that appeared 3\*n times (n is an integer), the bit can only present in numbers that appeared 3 times

e.g. 0010 0010 0010 1011 1011 1011 1000 (assuming 4-bit integers)\
2(0010) and 11(1011) appeared 3 times, and digit counts are:

> **Digits** 3 2 1 0
>
> **Counts** 4 0 6 3
>
> **Counts%3** 1 0 0 0

Counts on 2,1,0 are all times of 3, the only digit index that has Counts % 3 != 0 is 3

Therefore, to find the number that appeared only 1 or 2 times, we only need to extract all bits that has Counts %3 != 0

Now consider how we could do this by bit manipulation

since counts % 3 has only 3 states: 0(00),1(01),2(10)\
we could use a TWO BIT COUNTER (Two, One) to represent Counts % 3, now we could do a little research on state transitions, for each bit, let B be the input bit, we can enumerate the all possible state transitions, Two+, One+ is the new state of Two, One. (here we need to use some knowledge in Digital Logic Design)

> Two One B Two+ One+
>
> 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
>
> 1 1 0 X X (X represents we don't care)
>
> 1 1 1 X X

We could then draw the [**Karnaugh map**](https://celiachien.github.io/2020/10/02/%E5%8D%A1%E8%AF%BA%E5%9B%BE/#more) to analyze the logic, and then we get:

> One+ = (One ^ B) & (\~Two)
>
> Two+ = (\~One+) & (Two ^ B)

Now for int\_32, we need only 2 int\_32 two represent Two and One for each bit and update Two and One using the rules derived above

```cpp
class Solution {
  public:
    int singleNumber(vector<int>& nums) {
        int counterOne = 0;
        int counterTwo = 0;
        
        for (int i = 0; i < nums.size(); i++){
            counterOne = (~counterTwo) & (counterOne ^ nums[i]);
            counterTwo = (~counterOne) & (counterTwo ^ nums[i]);
        }
        return counterOne;
    }
};
```

### 解法


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/linear-list/array/single-number-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.