Category: JavaScript Programming

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 result to 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:

• result starts at 0.
• For each num in array, XOR it with result.
• 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:

• result initialized as 0.
• 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

• LeetCode 260. Single Number III
• LeetCode 137. Single Number II

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.