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
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

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

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala