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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala