### Integer to Roman conversion - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

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

Problem Statement Roman numerals are represented by seven different symbols: I…

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

Its every software engineer’s dream to work with the big FAANG companies…

It is one of a simple algorithm to study for a beginner to understanding sorting…

** Inversion There is an array(a) and two indexes i and j. Inversion is the…

Counting sort runs on relatively smaller set of input. Counting sort calculates…

Introduction This post has the complete code to send email through smtp server…

Introduction In a normal email sending code from python, I’m getting following…

Introduction In one of my app, I was using to talk to . I have used some event…

Introduction So you have a Django project, and want to run it using docker image…

Introduction It is very important to introduce few process so that your code and…

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…