### 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**- LeetCode - Single Number
- LeetCode - Single Number 2
- LeetCode - Single Number 3
- Find XOR from 1 to n Numbers
- LeetCode - Number of 1 bit

## Comments

## Post a Comment