### Min Priority Queue Implementation with Heap Data structure

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

September 01, 2020

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

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

```
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;
}
```

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

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.

```
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;
}
```

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

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

```
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])) {
set.add(nums[i]);
uniqueElementSum += nums[i];
}
//all sum
sum += nums[i];
}
return 2 * uniqueElementSum - sum;
}
```

We require a `HashSet`

just to check for unique elements.

The complexity is `O(n)`

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

Problem Statement Given an array nums of n integers, are there elements a, b, c…

Big-O notation In simpler terms, its kind of a unit to measure how efficient an…

Here are some tips while giving your coding interviews. 1. Never try to jump to…

A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…

This is kind of preliminary technique of sorting. And, this is the first…

Introduction Strapi is a backend system provides basic crud operations with…

Introduction I had to create many repositories in an Github organization. I…

Introduction I was trying to download some youtube videos for my kids. As I have…

Introduction In this post, we will explore some useful command line options for…

Introduction In this post, we will see how we can apply a patch to Python and…

Introduction We will introduce a Package Manager for Windows: . In automations…