# Single Number - Leet Code Solution

September 01, 2020

## Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Example

``````Input: [2,2,1]
Output: 1

Input: [4,1,2,1,2]
Output: 4``````

## Solution using Extra Memory

We can take help of `HashMap` where we can save numbers and their counts.

• In first iteration, just fill this `HashMap`
• Iterate over this `HashMap`, and find the number whose count is not 2

### Code

``````public int singleNumber_extraMemory(int[] nums) {
int l = nums.length;

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i=0; i<l; i++) {
Integer count = map.get(nums[i]);
if (count == null) {
count = 1;
}
else {
count ++;
}

map.put(nums[i], count);
}

for (Integer key : map.keySet()) {
if (map.get(key) != 2) {
return key;
}
}
return -1;
}``````

### Complexity

The complexity of above code is `O(n)`

## Solution using Sorting

If we can sort the numbers, then we will have all pair of numbers adjascent to each other.
Then, we can check pair of numbers where they are not equal.

### Code

``````public int singleNumber_sort(int[] nums) {
int l = nums.length;

Arrays.sort(nums);
int i=0;
while (i<l-1) {
if (nums[i] != nums[i+1]) {
return nums[i];
}

i += 2;
}
//check for last element
if (l % 2 == 1) {
return nums[l-1];
}
return -1;
}``````

### Complexity

Since we are sorting, and iterating over array once. The complexity is `O(nlogn)`

## Solution using Simple Maths

Assuming our array has all pairs. i.e. we don’t have a single number. Then, following is true:

``2 (sum of unique numbers) = (sum of all numbers)``

Now, if we know one of the number is missing in pairs. Following must be true:

``2 (sum of unique numbers) - (sum of all numbers) = Missing Number``

Lets take a look at example:

``````#input [2, 2, 1]

2 * (2 + 1) - (2 + 2 + 1)
= 6 - 5
= 1
Result = 1

#Another example
# input [4,1,2,1,2]
2 * (4 + 1 + 2) - (4+1+2+1+2)
= 14 - 10
= 4
Result = 4``````

### Code

``````public int singleNumber(int[] nums) {
int l = nums.length;
Set<Integer> set = new HashSet<>();

int sum = 0;
int uniqueElementSum = 0;

for (int i=0; i<l; i++) {
if (!set.contains(nums[i])) {
uniqueElementSum += nums[i];
}

//all sum
sum += nums[i];
}

return 2 * uniqueElementSum - sum;
}``````

We require a `HashSet` just to check for unique elements.

### Complexity

The complexity is `O(n)`

## Similar Posts

System design interview is pretty common these days, specially if you are having…

### Check whether an integer number given is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

### Add two numbers(reverse order) link list Problem - Leet Code Solution

Problem Statement You are given two non-empty linked lists representing two non…

### Magical usage of Bitwise operators - Get optimized solutions for many arithmatic problems

Introduction I will list some of the interesting usage of bitwise operators…

### Valid Anagrams - Leet Code Solution

Problem Statement Given two strings s and t , write a function to determine if t…

### Max Priority Queue Implementation with Heap Data structure

Max Priority Queue is a data structure which manage a list of keys(values). And…

## Latest Posts

Introduction I was trying to upload images to my backend using rest APIs. I was…

### Spring - Learn Multiple Ways to use PackageScan Annotation

Introduction In this post, we will see multiple ways to use annotation…

Introduction I was using Paypal payment on one of my website, and suddenly lot…