Problem Statement
Given an array nums of length n, every integer in the array appears twice except for two integers. Identify and return the two integers that appears only once in the array. Return the two numbers in ascending order.
For example, if nums = [1, 2, 1, 3, 5, 2], the correct answer is [3, 5], not [5, 3]
Examples
Example 1:
Input : nums = [1, 2, 1, 3, 5, 2]
Output : [3, 5]
Explanation : The integers 3 and 5 have appeared only once.Example 2:
Input : nums = [-1, 0]
Output : [-1, 0]
Explanation : The integers -1 and 0 have appeared only once.Different Approaches
1️⃣Brute Force Approach
Intuition:
The brute force way to solve this will be to utilize a frequency counting approach. By keeping track of the frequency of each element in the array, the element that appears only once can be easily identified.
Approach:
- Use a hash map to store the frequency of each element in the array. The keys of the map are the elements of the array, and the values are their corresponding frequencies.
- Traverse the entire array once, and for each element, update its frequency count in the map.
- After populating the map with frequency counts, iterate over the map to find the elements with a frequency of 1. Add these elements in the result array.
- Return the resulting array after sorting it.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the single
number in the given array */
vector<int> singleNumber(vector<int>& nums){
// Array to store the answer
vector<int> ans;
/* Map to store the elements
and their frequencies */
unordered_map <int, int> mpp;
// Iterate on the array
for(int i=0; i < nums.size(); i++) {
mpp[nums[i]]++; // Update the map
}
// Iterate on the map
for(auto it : mpp) {
// If frequency is 1
if(it.second == 1) {
/* Add the element to
the result array */
ans.push_back(it.first);
}
}
// Return the result after sorting
sort(ans.begin(), ans.end());
return ans;
}
};
int main() {
vector<int> nums = {1, 2, 1, 3, 5, 2};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the single
number in the given array */
vector<int> ans = sol.singleNumber(nums);
cout << "The single numbers in given array are: " << ans[0] << " and " << ans[1];
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N)(where N is the size of the array)- Traversing the array to update the Hash Map - O(N).
- Traversing on the map - O(N) (in worst case).
- Sorting the answer array - O(2*log(2)) ~ O(1).
- Hence, O(N) + O(N) + O(1) ~ O(N).
- Space Complexity:
O(N), Using a hashmap data structure and in the worst-case (when all elements in the array are unique), it will store N key-value pairs.
2️⃣ Optimal Approach (Bit Manipulation)
Intuition:
An optimal approach to solve this problem will be possible if we can divide the elements in array into two groups such that each group only contains one unique element. This way, the problem boils down to Single Number-I and both the unique elements can be identified with ease.
Now, to divide the numbers into two groups(buckets), the rightmost set bit in the overall XOR of all elements can be used. The overall XOR of all elements is equivalent to the XOR of the two unique numbers.
Why Divide using the Rightmost Set Bit?
This is because of the following reasons:
- The two unique numbers needs to be separated into two different groups, and the rightmost set bit in the overall XOR will indicate the bit position where the the two unique numbers differ.
- Using this bit, all the elements in the array can be divided into two groups (buckets):
- One group where this bit is set.
Another group where this bit is not set.
Approach:
- Traverse the entire array, performing an XOR operation on all numbers. This will effectively cancel out all the numbers that appear twice, leaving us with the XOR of the two unique numbers.
- Determine the rightmost set bit (bit that is 1) in the result from the first step. This set bit can be used to differentiate the two unique numbers since they must differ at this bit position.
- Traverse the array again, but this time divide the numbers into two groups:
- One group where the numbers have the rightmost set bit.
- Another group where the numbers do not have this bit set.
- Perform XOR operations while adding numbers in each group. This will cancel out the duplicate numbers, leaving only the unique numbers in each group.
- Sort the two unique numbers in ascending order and return them.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the single
numbers in the given array */
vector<int> singleNumber(vector<int>& nums){
// Variable to store size of array
int n = nums.size();
// Variable to store XOR of all elements
long XOR = 0;
// Traverse the array
for(int i=0; i < n; i++) {
// Update the XOR
XOR = XOR ^ nums[i];
}
/* Variable to get the rightmost
set bit in overall XOR */
int rightmost = (XOR & (XOR - 1)) ^ XOR;
// OR
// int rightmost = XOR & -XOR;
// this isolates the rightmost set bit
/* Variables to stores XOR of
elements in bucket 1 and 2 */
int XOR1 = 0, XOR2 = 0;
// Traverse the array
for(int i=0; i < n; i++) {
/* Divide the numbers among bucket 1
and 2 based on rightmost set bit */
if(nums[i] & rightmost) {
XOR1 = XOR1 ^ nums[i];
}
else {
XOR2 = XOR2 ^ nums[i];
}
}
// Return the result in sorted order
if(XOR1 < XOR2) return {XOR1, XOR2};
return {XOR2, XOR1};
}
};
int main() {
vector<int> nums = {1, 2, 1, 3, 5, 2};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the single
numbers in the given array */
vector<int> ans = sol.singleNumber(nums);
cout << "The single numbers in given array are: " << ans[0] << " and " << ans[1];
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), Traversing the array twice results inO(2*N). - Space Complexity:
O(1), Using a couple of variables i.e., constant space.