### Universal Solution of Single Number Problem - The Coding Shala

Home >> Programming >> Solution of Single Number Problem

In this post, we will learn how to solve the Single Number Problem using Bit Manipulation.

## Universal Solution of Single Number Problem

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

#### Approach

If a number appears n times then the bitSum in ith(i in range 0 to 31) vertical level equals to n or 0. For example, if 2 appears 3 times then

2 => 1 0
2 => 1 0
2 => 1 0
---------
3 0

So if bitSum in ith level does not equal to n, then extra bit sum is coming from a single number that appears only once. In that case, the sum will be n+1(if the ith bit in a single number is 1).

So by checking all the bits sum we can find out a single number.

Java Program:

```class Solution {
public int singleNumber(int[] nums) {
int result = 0;
int n = 3;
//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 n or not
if(bitSum%n != 0) {
//make ith bit as 1
result = result | (1<<i);
}
}
return result;
}
}
```

Other Posts You May Like