Single Number LeetCode Solution C++ : Learn the most efficient way to solve the Single Number problem on LeetCode using C++ and the XOR bitwise operator. Understand time complexity, code explanation, and why this approach works.
Introduction of Single Number LeetCode Solution C++
Looking for an efficient Single Number LeetCode Solution in C++? You’re in the right place!
The Single Number problem is one of the most popular coding interview questions on platforms like LeetCode and helps test your understanding of bit manipulation.
Let’s dive in and see how you can solve it in linear time and constant space.
Problem Statement: Single Number
LeetCode 136. Single Number
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:
Input: nums = [4,1,2,1,2]
Output: 4
How to Solve the Single Number Problem
At first glance, you might think of using:
- Hash maps to count occurrences
- Sorting the array and checking neighbors
But both use extra space or more than O(n) time.
Instead, there’s a beautiful trick using the XOR bitwise operator.
Fantastic — let’s structure your blog to show progressive solutions to the Single Number problem:
✅ Brute-force solution (simplest but inefficient)
✅ Better (scalable) solution (using a map or set)
✅ Perfect solution (optimal XOR trick)
1. Brute Force Solution (O(n²))
Approach
- For each number, count how many times it appears in the array.
- Return the one that appears only once.
Code
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
if (count == 1) {
return nums[i];
}
}
return -1; // No single number found
}
};
Complexity
- Time: O(n²)
- Space: O(1)
✅ Easy to understand
❌ Slow for large arrays
2. Better Solution Using Hash Map (O(n))
Approach
- Use a hash map to count frequencies.
- Return the number whose frequency is 1.
Code
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> freq;
for (int num : nums) {
freq[num]++;
}
for (auto& pair : freq) {
if (pair.second == 1) {
return pair.first;
}
}
return -1;
}
};
Complexity
- Time: O(n)
- Space: O(n)
✅ Linear time
❌ Extra space required
3. Perfect Solution Using XOR (O(n), O(1))
Recall these properties of XOR (^):
a ^ a = 0(a number XOR itself is zero)a ^ 0 = a- XOR is commutative and associative (order doesn’t matter)
So if every number appears twice, XOR-ing all numbers cancels out the pairs:
a ^ a ^ b = 0 ^ b = b
Hence, the Single Number remains after XOR-ing all numbers.
C++ Code – Single Number LeetCode Solution
Here’s the optimized solution in C++ that you provided:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
};
Step-by-Step Code Explanation
Let’s break it down line by line.
Line 1
class Solution {
Defines a class named Solution as required by LeetCode’s online judge.
Line 2
public:
Marks methods as accessible outside the class.
Line 3
int singleNumber(vector<int>& nums) {
- Defines a function
singleNumber - Takes a reference to a vector of integers
nums - Returns an
int
Line 4
int result = 0;
- Initialize
resultto 0. - This variable will hold the XOR of all numbers.
Line 5
for (int num : nums) {
result ^= num;
}
- Loops through each integer in the array
nums. - XORs it with
result. - Duplicate numbers cancel each other out.
- Only the single number remains.
Example trace for [4,1,2,1,2]:
0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4
So the single number is 4.
Line 8
return result;
Returns the unique number found.
Time and Space Complexity
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
This solution is optimal and easily fits the problem’s constraints.
Summary
| Solution | Time | Space |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Hash Map | O(n) | O(n) |
| XOR (Optimal) | O(n) | O(1) |
Python Solution
Focus Keyword: Single Number LeetCode Solution Python
class Solution:
def singleNumber(self, nums):
result = 0
for num in nums:
result ^= num
return result
Explanation:
- Initialize
result = 0. - XOR each element into
result. - Pairs cancel out; single number remains.
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
Java Solution
Focus Keyword: Single Number LeetCode Solution Java
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
}
Explanation:
resultstarts at 0.- For each
numin array, XOR it withresult. - The unique number remains after all XORs.
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
JavaScript Solution
Focus Keyword: Single Number LeetCode Solution JavaScript
var singleNumber = function(nums) {
let result = 0;
for (let num of nums) {
result ^= num;
}
return result;
};
Explanation:
resultinitialized as0.- Loop through
nums. - XOR all numbers together.
- Duplicate numbers cancel out, leaving the single number.
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
Advantages of XOR Approach
- No extra data structures required
- Runs in linear time
- Simple and elegant logic
If you’re preparing for coding interviews, knowing this XOR trick can save you crucial time!
🔗 Related LeetCode Problems
Conclusion
The XOR trick is a brilliant way to solve the Single Number problem efficiently in C++. Understanding how XOR cancels out duplicate numbers is essential for solving similar problems in coding interviews.
FAQ – Single Number LeetCode Solution
Q1. What is the Single Number problem on LeetCode?
The Single Number problem on LeetCode asks you to find the only integer in an array that appears exactly once, while all other integers appear twice. You must solve it in linear time and with constant space complexity.
Q2. How does the XOR trick help solve the Single Number problem?
The XOR operator cancels out identical numbers because a ^ a = 0. When you XOR all numbers in the array, duplicates cancel each other, leaving only the unique number behind.
Q3. What is the time complexity of the XOR solution for Single Number?
The XOR solution runs in O(n) time, where n is the number of elements in the array.
Q4. What is the space complexity of the XOR solution for Single Number?
It uses O(1) space because you only store a single integer result, regardless of the input size.
Q5. Can the Single Number problem be solved without bit manipulation?
Yes, but less efficiently. You could use a hash map to count occurrences or sort the array and check neighbors. However, these methods either use extra space or exceed O(n) time complexity.
Q6. Can the Single Number problem be solved in Python, Java, or JavaScript?
Absolutely! The same XOR logic works in Python, Java, C++, JavaScript, and many other languages. It’s language-agnostic because XOR is a universal bitwise operation.
Q7. Is the XOR method safe for negative numbers?
Yes! XOR works on the bit-level representation of integers, so it handles negative numbers correctly.
Q8. What LeetCode problems are similar to Single Number?
- Single Number II (LeetCode 137) – Find the number appearing only once when every other appears three times.
- Single Number III (LeetCode 260) – Find two numbers appearing once when every other appears twice.
Q9. Why can’t I just sort the array to solve Single Number?
While sorting works, it’s O(n log n) time, which doesn’t meet the problem’s linear time requirement. The XOR method is faster and uses constant space.
Q10. Is Single Number a common coding interview question?
Yes! The Single Number problem is frequently asked in coding interviews because it tests knowledge of bit manipulation, time complexity, and space optimization.
Leave a Reply