> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/array/easy/137.-single-number-ii.md).

# 137. Single Number II

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [2,2,3,2]
</strong><strong>Output: 3
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0,1,0,1,0,1,99]
</strong><strong>Output: 99
</strong></code></pre>

&#x20;

**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**.

## Intuition

```
Approach 1: 
Take all store count in hashmap and move along
Uses extra space of n

Approach 2:
Lets take an example

5 5 5 4
Binary
1 0 1
1 0 1
1 0 1
1 0 0

Now in each col count ones and take mod3
So only 1 0 0 remains

TC- n*d(32 bits)
```

### Links

<https://leetcode.com/problems/single-number-ii/description/>

### Video Links

### Approach 1:

```
Hash map
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> mp;

        for(int i=0; i<nums.size(); i++)
            mp[nums[i]]++;

        for(auto &it: mp)
            if(it.second == 1)
                return it.first;

        return 0;
    }
};
```

{% endcode %}

### Approach 2:

```
Bits approach
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> count(32,0);

        for(auto &it: nums){
            int temp = it;
            for(int i=0; i<32; i++){
                if(temp&1){
                    count[i]++;
                    count[i]=count[i]%3;
                }
                temp>>=1;
            }
        }

        int ans = 0;

        for(int i=0; i<32; i++){
            if(count[i] == 0)    continue;

            int temp = 1<<i;
            ans |= temp;
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 3:

```
Bits extra loop optimized
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    int ans = 0;

    for (int i = 0; i < 32; ++i) {
      int sum = 0;
      for (const int num : nums)
        sum += num >> i & 1;
      sum %= 3;
      ans |= sum << i;
    }

    return ans;
  }
};
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###