Single Number

Yogesh Bhalerao
Last Updated: May 13, 2022

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.
 

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:

Input: nums = [2,2,1]

Output: 1

 

Example 2:

Input: nums = [1]

Output: 1

 

In this article, we are going to see many solutions. 

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.

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

 

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! 

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think