# Single Number II Problem

## Description

LeetCode Problem 137.

Given an integer array nums whereevery element appears three times except for one, which appears exactly once. Find the single element and return it.

You mustimplement a solution with a linear runtime complexity and useonly constantextra space.

Example 1:

``````1
2
Input: nums = [2,2,3,2]
Output: 3
``````

Example 2:

``````1
2
Input: nums = [0,1,0,1,0,1,99]
Output: 99
``````

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• Each element in nums appears exactly three times except for one element which appears once.

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = nums.size();
long ans;
int x, t;
ans = 0;
int p = 0;
// We have 32 bits integers as input
for(int i = 0; i < 32; i++) {
t = 0;
//calculate sum of ith bit for all numbers in nums
for(int j = 0; j < n;j++) {
x = nums[j] & 1;
t = t + x;
nums[j] = nums[j] >> 1;
}
t = t % 3;
//the bit that does not occur as multiple of 3 is left as a remainder
ans = ans + t * pow(2, p);
p++;
}
return ans;
}
};
``````