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;
}
You can also try this code with Online C++ Compiler
#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;
}
You can also try this code with Online C++ Compiler
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;
}
You can also try this code with Online C++ Compiler
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;
}
You can also try this code with Online C++ Compiler
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!
84+ registered