## Solution:

**Using Extra Memory**

We can use __HashMap __to keep track of numbers and their counts.

- Fill this HashMap in the first iteration.
- Iterate through this HashMap and locate the number with a count of less than two.

```
#include<iostream>
#include<unordered_map>
using namespace std;
int singleNumber_extraMemory(int arr[],int n){
unordered_map<int,int> m;
for(int i=0;i<n;i++){
int count=m[arr[i]];
if(count==0){
count=1;
}
else{
count++;
}
m[arr[i]]=count;
}
for(auto& it: m){
if(it.second!=2){
return it.first;
}
}
return -1;
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<singleNumber_extraMemory(arr,n)<<endl;
}
```

```
#include<iostream>
#include<unordered_map>
using namespace std;
int singleNumber_extraMemory(int arr[],int n){
unordered_map<int,int>m;
for(int i=0;i<n;i++){
int count=m[arr[i]];
if(count==0){
count=1;
}
else{
count++;
}
m[arr[i]]=count;
}
for(auto& it: m){
if(it.second!=2){
return it.first;
}
}
return -1;
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<singleNumber_extraMemory(arr,n)<<endl;
}
```

**Input:**

Input consists of n, which is the size of the array, and then n elements.

```
5
4 1 2 1 2
```

**Output:**

`4`

**Time Complexity**: O(n) as we have to iterate all the elements present in the array. Where n is the no. of elements in the array.

**Space complexity**: O(n), As we require, extra space of unordered map that consists of all the elements of the array.

**Using Sorting**

We will have all pairs of numbers adjacent to each other if we can sort the numbers. Then we can look for a pair of numbers that aren't equal.

```
#include<bits/stdc++.h>
using namespace std;
int singleNumber_sort(int arr[],int n){
sort(arr,arr+n);
int i=0;
while(i<n-1){
if(arr[i]!=arr[i+1]){
return arr[i];
}
i+=2;
}
//checking for the last element
if(n%2==1){
return arr[n-1];
}
return -1;
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<singleNumber_sort(arr,n)<<endl;
}
```

**Input**

Input consists of **n**, which is the size of the array and then n elements.

```
5
4 1 2 1 2
```

**Output**

`4`

**Time Complexity: **O(n logn) as we have to sort all the elements in the array first where n is the no. of elements in the array.

**Space Complexity:**O(1), As we do not require extra space.

**Using Simple Maths**

Assuming we have all pairings in our array. We don't have a single number, in other words. Then, the following is true:

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

If we know that one of the numbers in a pair is missing, we can proceed. The following conditions must be satisfied,array elements

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

```
#include<bits/stdc++.h>
using namespace std;
int singleNumber(int arr[],int n){
unordered_set<int>s;
int sum=0;
int uniqueSum=0;
for(int i=0;i<n;i++){
if(s.find(arr[i])==s.end()){
s.insert(arr[i]);
uniqueSum+=arr[i];
}
sum+=arr[i];
}
return 2*uniqueSum-sum;
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<singleNumber(arr,n)<<endl;
}
```

**Input: **

Input consists of n which is the size of the array and then n elements.

```
5
4 1 2 1 2
```

**Output:**

`4`

**Time Complexity**: O(n) as we have to iterate all the elements in the array first, where n is the no. of elements in the array.

**Space complexity**: O(n), As we require extra space using set.

Check out this problem - __Pair Sum In Array__.

## Frequently Asked Questions:

**Q. What is the time complexity of the sorting function?**

Sol: O(n logn) is time complexity for the sorting function

**Q. How is an unordered_map implemented in C++?**

Sol: Unordered map is implemented with the help of hash tables

**Also Read - **Strong number in c

## Key Takeaways:

This blog discussed different approaches to the problem â€śSingle Numberâ€ť with time and space complexity with its implementation in Java. The above problem is critical from the interview aspect as it is asked frequently in the interviews. So make sure you do practice and understand the concept thoroughly before attempting.

If you feel confident, then why donâ€™t you give it a try by submitting it here? __Single Number__.

If you are a beginner in coding and want to learn DSA, you can look for our__ guided path for DSA__, which is free!