1.
Introduction
2.
Problem statement for Single Number
3.
Solution:
3.1.
Using Extra Memory
3.2.
Using Sorting
3.3.
Using Simple Maths
4.
5.
Key Takeaways:
Last Updated: Mar 27, 2024

# Single Number

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

Todayâ€™s problem, i.e., â€“â€śSingle Number,â€ť is highly asked in product-based companies like Amazon, Google, and Microsoft.

Weâ€™ll go over all the methods, including brute force and the most efficient way to solve this problem.

Without further ado, letâ€™s get started with the problem statement.
Recommended topic, kth largest element in an array and Euclid GCD Algorithm

## Problem statement for Single Number

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

Example 1:

Example 2:

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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.

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!

Live masterclass