Find the Single Number in an Array
Find the Single Number in an Array
In a given array of integers, every element appears twice except for one number.
Your task is to identify the integer that appears only once, using an efficient algorithm that operates in linear time and constant space.
Problem Overview
You are provided with a non-empty array called nums, where each integer appears exactly twice, except for one unique number that appears only once. The challenge is to find that lone number with the following constraints:
- Time Complexity: O(n)
- Space Complexity: O(1)
The array can contain up to 10,000 elements, and the values within the array range from -10,000 to 10,000.
Example Scenarios
Let’s look at two examples to better understand the problem:
In this case, the number 3 appears twice, and the number 2 appears only once.
Here, 7 and 6 appear twice, but 8 appears only once.
Problem Constraints:
- The length of the array is between 1 and 10,000.
- The values in the array range from -10,000 to 10,000.
Given these constraints, your solution must be efficient both in terms of time and space.
Efficient Solution: XOR Approach
The key to solving this problem efficiently is using the XOR operation. XOR has a unique property that makes it particularly useful in this scenario:
- x ^ x = 0 (Any number XORed with itself results in 0).
- x ^ 0 = x (Any number XORed with 0 results in the number itself).
- XOR is both commutative and associative, meaning the order of operations doesn’t matter.
Thus, when you XOR all the numbers in the array, the numbers that appear twice will cancel each other out, leaving only the number that appears once.
Pair with Given Sum - 2Sum Solution
Recommendation – You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would be to check every pair of numbers in the array. This would be an O(n^2) solution. Can you think of a better way? Maybe in terms of mathematical equation?
Hint 2:
Given, We need to find indices i and j such that i != j and nums[i] + nums[j] == target. Can you rearrange the equation and try to fix any index to iterate on?
Hint 3:
Iterate through the array while checking if target – nums[i] exists in the hash map. If not, store the current element with its index in the hash map and continue. This ensures O(1) lookups.
There are mainly 4 approach to solve this problem –
- Brute Force Method
- Sorting Method
- Hash Map(Two Pass) Method
- Hash Map(One Pass) Method
1. Brute Force Method
This method check all possible pairs of numbers in the array to find the ones that add up to the target. Simple but slow for large arrays.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
class Solution:
def singleNumber(self, nums: List[int]) -> int:
for i in range(len(nums)):
flag = True
for j in range(len(nums)):
if i != j and nums[i] == nums[j]:
flag = False
break
if flag:
return nums[i]
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
}
2. Sorting Method
This method sort the array, then use two pointers (one at the start and one at the end) to find the pair that sums to the target.
- Time complexity: O(nlogn)
- Space complexity: O(n)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
vector> A;
for (int i = 0; i < nums.size(); i++) {
A.push_back({nums[i], i});
}
sort(A.begin(), A.end());
int i = 0, j = nums.size() - 1;
while (i < j) {
int cur = A[i].first + A[j].first;
if (cur == target) {
return {min(A[i].second, A[j].second),
max(A[i].second, A[j].second)};
} else if (cur < target) {
i++;
} else {
j--;
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[][] A = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
A[i][0] = nums[i];
A[i][1] = i;
}
Arrays.sort(A, Comparator.comparingInt(a -> a[0]));
int i = 0, j = nums.length - 1;
while (i < j) {
int cur = A[i][0] + A[j][0];
if (cur == target) {
return new int[]{Math.min(A[i][1], A[j][1]),
Math.max(A[i][1], A[j][1])};
} else if (cur < target) {
i++;
} else {
j--;
}
}
return new int[0];
}
}
class Solution:
def singleNumber(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return list(seen)[0]class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
let A = [];
for (let i = 0; i < nums.length; i++) {
A.push([nums[i], i]);
}
A.sort((a, b) => a[0] - b[0]);
let i = 0, j = nums.length - 1;
while (i < j) {
let cur = A[i][0] + A[j][0];
if (cur === target) {
return [Math.min(A[i][1], A[j][1]),
Math.max(A[i][1], A[j][1])];
} else if (cur < target) {
i++;
} else {
j--;
}
}
return [];
}
}
3. Hash Set
This method first, store all numbers and their indices in a hash map. Then, iterate again to find if the complement (target – current number) exists in the map.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_map indices; // val -> index
for (int i = 0; i < nums.size(); i++) {
indices[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if (indices.count(diff) && indices[diff] != i) {
return {i, indices[diff]};
}
}
return {};
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map indices = new HashMap<>(); // val -> index
for (int i = 0; i < nums.length; i++) {
indices.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (indices.containsKey(diff) && indices.get(diff) != i) {
return new int[]{i, indices.get(diff)};
}
}
return new int[0];
}
}
class Solution:
def singleNumber(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return list(seen)[0]
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
twoSum(nums, target) {
const indices = {}; // val -> index
for (let i = 0; i < nums.length; i++) {
indices[nums[i]] = i;
}
for (let i = 0; i < nums.length; i++) {
let diff = target - nums[i];
if (indices[diff] !== undefined && indices[diff] !== i) {
return [i, indices[diff]];
}
}
return [];
}
}
4. Bit Manipulation
Bit manipulation refers to the process of directly operating on the individual bits of a number. In binary, all data is represented as a series of bits (0s and 1s).
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
int singleNumber(vector& nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
};
public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res = num ^ res
return res
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
singleNumber(nums) {
let res = 0;
for (const num of nums) {
res ^= num;
}
return res;
}
}
