### 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**- LeetCode - Single Number
- Find XOR from 1 to n Numbers
- LeetCode - Bulb Switcher
- LeetCode - Simple XML Validator
- LeetCode - Degree of an Array

## Comments

## Post a Comment