Single Number solution and explanation
Google
TCS
Cisco
9 more videos on this problem
Single Number - Leetcode 136 - PythonNeetCode · 7:09 · 148K views
L5. Single Number-I | Bit Manipulationtake U forward · 7:12 · 124K views
Single non-repeating element in an array (LeetCode 136) | Full solution with ExamplesNikhil Lohia · 8:46 · 56K views
LeetCode Single Number Solution Explained - JavaNick White · 6:06 · 32K views
Single Number | LeetCode problem 136 | Top 150 interview question seriesTechnosage · 5:26 · 24K views
Single Number - Leetcode 136 - Bit Manipulation (Python)Greg Hogg · 3:40 · 22K views
Leetcode | 136. Single Number | Easy | Java Solution [2 Solutions]Developer Docs · 6:39 · 4K views
LeetCode 136: Single Number [Python]Frederik Müller · 11:10 · 2K views
LeetCode 136: Single Number - Interview Prep Ep 35Fisher Coder · 15:18 · 2K views
Solve a LeetCode Problem Step by Step | 136. Single NumberJovian · 11:15 · 1K views
The problem
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
Constraints:
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- Each element in the array appears twice except for one element which appears only once.
Approach overview
Problem Overview: You receive an integer array where every element appears exactly twice except for one element that appears only once. The task is to find that single element. The solution must work efficiently even when the array grows large.
Approach 1: Hash Map Counting (O(n) time, O(n) space)
This approach uses a frequency map to count how many times each number appears. Iterate through the array and store counts using a hash map where the key is the number and the value is its frequency. After building the map, scan through the entries and return the number with frequency 1. The logic is straightforward and easy to implement, which makes it a good baseline approach when you first reason about the problem. However, it requires extra memory proportional to the number of unique elements.
This technique relies on constant-time hash lookups and works well for many array counting problems. The tradeoff is memory usage since the hash map stores up to n keys.
Approach 2: XOR Operation (O(n) time, O(1) space)
The optimal solution uses properties of the XOR bitwise operator. XOR has two useful rules: a ^ a = 0 and a ^ 0 = a. When you XOR all numbers in the array together, duplicate numbers cancel each other out because each pair produces zero. The only value left after the full pass is the number that appears once.
Implementation is simple: initialize a variable result = 0, iterate through the array, and update result ^= num for each element. After processing the entire array, result holds the unique element. The algorithm performs a single pass and uses only one variable for storage, giving constant extra space.
This approach is a classic example of using bit manipulation to reduce memory usage. It avoids auxiliary data structures while maintaining linear runtime, which makes it both elegant and efficient.
Recommended for interviews: Interviewers usually expect the XOR solution. Starting with the hash map approach demonstrates you understand the problem using counting and hash lookups. Moving to the XOR technique shows deeper algorithmic thinking and familiarity with bitwise operations. The XOR solution achieves the optimal O(n) time and O(1) space, which is the key improvement interviewers look for.
Approach 1: Approach 1: XOR Operation
This approach leverages the properties of XOR bitwise operation. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. Thus, XORing all elements in the array results in getting the single number because all other numbers cancel themselves out.
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result
nums = [2, 2, 1]
print(singleNumber(nums)) # Output: 1public class SingleNumber {
public static int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 2, 1};
System.out.println(singleNumber(nums)); // Output: 1
}
}#include <iostream>
#include <vector>
int singleNumber(std::vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
int main() {
std::vector<int> nums = {2, 2, 1};
std::cout << singleNumber(nums) << std::endl; // Output: 1
return 0;
}function singleNumber(nums) {
let result = 0;
for (let num of nums) {
result ^= num;
}
return result;
}
const nums = [2, 2, 1];
console.log(singleNumber(nums)); // Output: 1#include <stdio.h>
int singleNumber(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; ++i) {
result ^= nums[i];
}
return result;
}
int main() {
int nums[] = {2, 2, 1};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", singleNumber(nums, numsSize)); // Output: 1
return 0;
}using System;
public class SingleNumberSolution {
public static int SingleNumber(int[] nums) {
int result = 0;
foreach (int num in nums) {
result ^= num;
}
return result;
}
public static void Main() {
int[] nums = {2, 2, 1};
Console.WriteLine(SingleNumber(nums)); // Output: 1
}
}The singleNumber function iteratively applies the XOR operation on the list of numbers. The duplicates nullify themselves leaving the single number.
Time Complexity: O(n) - Iterates over the list once.
Space Complexity: O(1) - Uses only one variable for storage.
Approach 2: Approach 2: Hash Map
In this approach, we use a hash map (or dictionary) to count occurrences of each number. The single number will have a count of 1. This isn't the optimal solution in terms of extra space but is valid if space was not constrained.
def singleNumber(nums):
count_map = {}
for num in nums:
count_map[num] = count_map.get(num, 0) + 1
for key, count in count_map.items():
if count == 1:
return key
nums = [4, 1, 2, 1, 2]
print(singleNumber(nums)) # Output: 4import java.util.HashMap;
public class SingleNumber {
public static int singleNumber(int[] nums) {
HashMap<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
for (int key : countMap.keySet()) {
if (countMap.get(key) == 1) {
return key;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 1, 2, 1, 2};
System.out.println(singleNumber(nums)); // Output: 4
}
}#include <iostream>
#include <unordered_map>
#include <vector>
int singleNumber(std::vector<int>& nums) {
std::unordered_map<int, int> countMap;
for (int num : nums) {
countMap[num]++;
}
for (const auto& pair : countMap) {
if (pair.second == 1) return pair.first;
}
return -1;
}
int main() {
std::vector<int> nums = {4, 1, 2, 1, 2};
std::cout << singleNumber(nums) << std::endl; // Output: 4
return 0;
}function singleNumber(nums) {
const countMap = {};
for (const num of nums) {
countMap[num] = (countMap[num] || 0) + 1;
}
for (const key in countMap) {
if (countMap[key] === 1) return parseInt(key);
}
return -1;
}
const nums = [4, 1, 2, 1, 2];
console.log(singleNumber(nums)); // Output: 4#include <stdio.h>
#include <stdlib.h>
int singleNumber(int* nums, int numsSize) {
int *hash = (int*)calloc(60001, sizeof(int));
for (int i = 0; i < numsSize; ++i) {
hash[nums[i] + 30000]++;
}
int result = 0;
for (int i = 0; i < 60001; ++i) {
if (hash[i] == 1) {
result = i - 30000;
break;
}
}
free(hash);
return result;
}
int main() {
int nums[] = {4, 1, 2, 1, 2};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", singleNumber(nums, numsSize)); // Output: 4
return 0;
}using System;
using System.Collections.Generic;
public class SingleNumberSolution {
public static int SingleNumber(int[] nums) {
Dictionary<int, int> countMap = new Dictionary<int, int>();
foreach (int num in nums) {
if (countMap.ContainsKey(num))
countMap[num]++;
else
countMap[num] = 1;
}
foreach (var pair in countMap) {
if (pair.Value == 1) return pair.Key;
}
return -1;
}
public static void Main() {
int[] nums = {4, 1, 2, 1, 2};
Console.WriteLine(SingleNumber(nums)); // Output: 4
}
}The Python function uses a dictionary (count_map) to count how often each number occurs and then identifies the one with a single occurrence.
Time Complexity: O(n) - Processing the entire list for both storing and checking.
Space Complexity: O(n) - Extra space for storing counts of elements in the dictionary.
Approach 3: Bitwise Operation
The XOR operation has the following properties:
- Any number XOR 0 is still the original number, i.e.,
x \oplus 0 = x; - Any number XOR itself is 0, i.e.,
x \oplus x = 0;
Performing XOR operation on all elements in the array will result in the number that only appears once.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function singleNumber(nums: number[]): number {
return nums.reduce((r, v) => r ^ v);
}func singleNumber(nums []int) (ans int) {
for _, v := range nums {
ans ^= v
}
return
}class Solution {
func singleNumber(_ nums: [Int]) -> Int {
return nums.reduce(0, ^)
}
}impl Solution {
pub fn single_number(nums: Vec<i32>) -> i32 {
nums.into_iter().reduce(|r, v| r ^ v).unwrap()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: XOR Operation | Time Complexity: O(n) - Iterates over the list once. |
| Approach 2: Hash Map | Time Complexity: O(n) - Processing the entire list for both storing and checking. |
| Bitwise Operation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Counting | O(n) | O(n) | When simplicity and clarity matter more than memory usage |
| XOR Bit Manipulation | O(n) | O(1) | Best general solution when duplicates appear exactly twice |
Frequently asked questions
Is Single Number easy or hard?
Single Number is categorized as an Easy problem on LeetCode. The hash map solution is simple to implement, while the XOR solution introduces a useful bit manipulation trick that appears in many technical interviews.
Single Number Python/Java solution
In Python or Java, the typical solution iterates through the array and XORs each element with a running variable. For example, start with result = 0 and update result ^= num for every value. After the loop finishes, result contains the single non-duplicated number.
How to solve Single Number in O(n)?
Iterate through the array and apply XOR with an accumulator variable. Because XOR cancels duplicate numbers, every pair disappears during the process. After processing all elements, the accumulator holds the element that appears once. The algorithm requires one pass and constant memory.
What is the best approach for Single Number?
The XOR bit manipulation approach is the best solution. By XORing all numbers in the array, duplicate values cancel each other out because a ^ a = 0. The remaining value is the unique number. This method runs in O(n) time and uses O(1) extra space.
Is Single Number asked at Google/Amazon/Meta?
Single Number is a common interview-style question used by companies like Amazon, Google, and Meta to evaluate understanding of bit manipulation and algorithmic reasoning. Variations of the problem often appear in coding screens and technical interviews.
What data structure is used in Single Number?
Two common techniques are used: a hash map for frequency counting and bit manipulation using XOR. The hash map approach stores counts for each number, while the XOR approach avoids extra data structures and relies on bitwise properties.
What is the time complexity of Single Number?
The optimal solution runs in O(n) time because the algorithm scans the array once and performs a constant-time XOR operation for each element. Space complexity is O(1) since only a single variable is used to track the result.