### Single Number 2 LeetCode Solution - The Coding Shala

Home >> LeetCode >> Single Number 2

In this post, we will learn how to solve LeetCode's Single Number 2 problem and will implement its solution in Java.

## Single Number 2 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.

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

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

## Single Number 2 Java Solution

Approach 1

We can use HashMap to store the count of numbers.

Java Program:

```class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
if(map.containsKey(num)) map.put(num, map.get(num)+1);
else map.put(num, 1);
}
for(int num : nums) {
if(map.get(num) == 1) return num;
}
return 0;
}
}
```

Approach 2

Using Bit Manipulation.

As we know every element appears three times except for one. If a number appears three times then if we do a vertical sum of their binary number 1 comes three times.

Let's take an example if 2 appears three times then:

2 => 1 0 (binary)
2 => 1 0
2 => 1 0
---------
now if we do vertical sum of every bit then
sum = 3 0

like this, if every element occurs three times then in their vertical sum every bit divides by 3 and if one element appears only once then that vertical bit sum will not divide by 3 so we need to figure out that bit only in our answer.

let's understand this by one example:

input: 2,2,23
We iterate vertically through the input all along 32 times(32 bits)
2 => 1 0
2 => 1 0
2 => 1 0
3 => 1 1
---------
4 1

so our single number is 1 1(3) since both the sum of the bits is not divisible by 3.

Java Program:

```class Solution {
public int singleNumber(int[] nums) {
int result = 0;

//finding vertical sum of bits
for(int i=0; i<32; i++) {
int bitSum = 0;
for(int num : nums) {
//add 1 in sum if bit is 1
bitSum += ((num >> i) & 1);
}

//now check if vertical sum is divided by 3 or not
if(bitSum%3 != 0) {
//make ith bit as 1
result = result | (1<<i);
}
}
return result;
}
}
```

Other Posts You May Like