What is the time complexity of Single Number?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Single Number?

This problem uses Array, Bit Manipulation. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Single Number?

**The 'self-cancelling' nature of XOR:** The most crucial insight is `X ^ X = 0`. This allows duplicate numbers to effectively 'erase' each other from the cumulative XOR sum, regardless of their position in the array. It's like they form a pair and disappear. **XOR's identity property for result preservation:** The property `X ^ 0 = X` ensures that the unique number, once all pairs have cancelled out, remains as the final accumulated result. Starting our `result` variable at `0` correctly leverages this identity element for XOR accumulation.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Single Number - LeetCode 136 Solution

Q: How to solve Single Number?

The elegance of the provided solution hinges entirely on the properties of the bitwise XOR operator (`^`). The core idea is that XORing a number with itself always yields zero (`A ^ A = 0`), and XORing any number with zero returns the number itself (`A ^ 0 = A`). Furthermore, XOR is both commutative and associative, meaning the order in which we perform XOR operations doesn't change the final result (e.g., `A ^ B ^ C` is the same as `C ^ A ^ B`). With these properties in mind, consider what happens when we XOR every number in the input array `nums` together, starting with an initial `result` of 0. When we encounter a number that appears twice, say `X`, it will contribute `X ^ X` to the cumulative XOR sum at some point. Since `X ^ X` evaluates to `0`, these pairs effectively cancel each other out, disappearing from the running total. Because of associativity, it doesn't matter if the two `X`'s are adjacent or separated by other numbers; their combined effect on the `result` will always be `0`. Consequently, after iterating through the entire array, all the numbers that appear twice will have 'XORed themselves out' to zero. The only number left standing in our `result` variable will be the unique element, XORed with zero (from the cancelled pairs and the initial `result`), which, by the `A ^ 0 = A` property, will simply be the unique number itself. This one-pass approach gives us linear time complexity, and since we only use a single `result` variable, it perfectly satisfies the constant extra space constraint.

Q: Which companies ask LeetCode 136. Single Number in interviews?

This problem is frequently asked at Airbnb, Cisco, Google, Nvidia, Palantir Technologies and 5 more companies.

Single Number - Complete Solution Guide

Single Number is LeetCode problem 136, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 * 10 4 -3 * 10 4 <= nums[i] <= 3 * 10 4 Each element in the array appears twice except for one element which appears only once.

Detailed Explanation

The 'Single Number' problem presents a deceptively simple challenge: given an array of integers where every number appears exactly twice, save for one unique outlier, your task is to pinpoint that lone number. For instance, in `[2,2,1]`, '1' is the one. In a more complex example like `[4,1,2,1,2]`, '4' is the elusive individual. The problem statement guarantees the array is non-empty and there's always exactly one number that doesn't have a pair. All numbers fit within a standard integer range. What elevates this problem beyond a straightforward counting exercise are the tight constraints. We're strictly mandated to achieve a solution with linear time complexity – meaning we can't afford to re-process the array multiple times or use algorithms with quadratic growth. Even more critically, we must accomplish this using only constant extra space. This immediately rules out common, intuitive approaches like building a frequency map (hash map/dictionary) to count occurrences, as that would consume space proportional to the number of unique elements, not a constant amount. The true puzzle lies in finding a mathematical or bitwise trick that can 'filter out' the pairs without storing them, leaving only the single number behind. It forces us to think beyond conventional data structures and leverage intrinsic properties of numbers themselves to meet the strict space requirement while still being efficient.

Solution Approach

The elegance of the provided solution hinges entirely on the properties of the bitwise XOR operator (`^`). The core idea is that XORing a number with itself always yields zero (`A ^ A = 0`), and XORing any number with zero returns the number itself (`A ^ 0 = A`). Furthermore, XOR is both commutative and associative, meaning the order in which we perform XOR operations doesn't change the final result (e.g., `A ^ B ^ C` is the same as `C ^ A ^ B`). With these properties in mind, consider what happens when we XOR every number in the input array `nums` together, starting with an initial `result` of 0. When we encounter a number that appears twice, say `X`, it will contribute `X ^ X` to the cumulative XOR sum at some point. Since `X ^ X` evaluates to `0`, these pairs effectively cancel each other out, disappearing from the running total. Because of associativity, it doesn't matter if the two `X`'s are adjacent or separated by other numbers; their combined effect on the `result` will always be `0`. Consequently, after iterating through the entire array, all the numbers that appear twice will have 'XORed themselves out' to zero. The only number left standing in our `result` variable will be the unique element, XORed with zero (from the cancelled pairs and the initial `result`), which, by the `A ^ 0 = A` property, will simply be the unique number itself. This one-pass approach gives us linear time complexity, and since we only use a single `result` variable, it perfectly satisfies the constant extra space constraint.

Step-by-Step Algorithm

Step 1: Initialize a variable `result` to 0. This will accumulate the XOR results.
Step 2: Iterate through the input array `nums`.
Step 3: For each number `num` in `nums`, perform a bitwise XOR operation: `result ^= num`.
Step 4: After iterating through all numbers, the `result` variable will hold the unique number.

Key Insights

**The 'self-cancelling' nature of XOR:** The most crucial insight is `X ^ X = 0`. This allows duplicate numbers to effectively 'erase' each other from the cumulative XOR sum, regardless of their position in the array. It's like they form a pair and disappear.
**XOR's identity property for result preservation:** The property `X ^ 0 = X` ensures that the unique number, once all pairs have cancelled out, remains as the final accumulated result. Starting our `result` variable at `0` correctly leverages this identity element for XOR accumulation.
**Bitwise operations for superior space efficiency:** Utilizing XOR bypasses the need for auxiliary data structures (like hash maps or frequency arrays) that would typically store counts. This characteristic of XOR perfectly meets the strict constant space complexity requirement without sacrificing linear time performance, making it an extremely elegant solution for this problem type.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Bit Manipulation.

Companies

Asked at: Airbnb, Cisco, Google, Nvidia, Palantir Technologies, Qualcomm, Yahoo, Yandex, Zoho, tcs.

Single Number | LeetCode 136

Easy

Array Bit Manipulation

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 136: Single Number - Detailed explanation and solution approaches.

Topics

Array Bit Manipulation

Companies

AirbnbCiscoGoogleNvidiaPalantir TechnologiesQualcommYahooYandex

Stats

Difficulty:Easy

Languages:4

Companies:10

Problem #:136

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Initialize a variable `result` to 0. This will accumulate the XOR results.
2
Step 2: Iterate through the input array `nums`.
3
Step 3: For each number `num` in `nums`, perform a bitwise XOR operation: `result ^= num`.
4
Step 4: After iterating through all numbers, the `result` variable will hold the unique number.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because the algorithm iterates through the array once. The space complexity is constant because only a single integer variable (`result`) is used to store the intermediate and final results, regardless of the input array's size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Hash Table Approach

Use a hash table (dictionary in Python) to count the occurrences of each number. Then, iterate through the hash table to find the number with a count of 1.

Time: O(n)Space: O(n)

Trade-offs: This approach is less efficient in terms of space complexity than the XOR approach. It's only preferable if the constraints on space complexity were relaxed.

Sorting Approach

Sort the array. Then, iterate through the sorted array, comparing adjacent elements. The unique element will not have a matching neighbor.

Time: O(n log n) - due to sortingSpace: O(1) or O(n) depending on sorting algorithm

Trade-offs: This approach has a higher time complexity than the XOR approach because of the sorting step. It's less efficient but could be considered if the XOR solution wasn't immediately apparent.

✨

Key Insights

1**The 'self-cancelling' nature of XOR:** The most crucial insight is `X ^ X = 0`. This allows duplicate numbers to effectively 'erase' each other from the cumulative XOR sum, regardless of their position in the array. It's like they form a pair and disappear.
2**XOR's identity property for result preservation:** The property `X ^ 0 = X` ensures that the unique number, once all pairs have cancelled out, remains as the final accumulated result. Starting our `result` variable at `0` correctly leverages this identity element for XOR accumulation.
3**Bitwise operations for superior space efficiency:** Utilizing XOR bypasses the need for auxiliary data structures (like hash maps or frequency arrays) that would typically store counts. This characteristic of XOR perfectly meets the strict constant space complexity requirement without sacrificing linear time performance, making it an extremely elegant solution for this problem type.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: The array contains only one element. The solution correctly returns that single element as it's the unique number.
Edge case 2: The array is empty. While the problem statement specifies a non-empty array, a robust solution might handle this by returning a default value (e.g., 0 or throwing an exception).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Misunderstanding the XOR operator's properties. Incorrectly assuming it performs addition or subtraction.

✗Common mistake 2: Not considering edge cases, such as an empty array or an array with only one element. A robust solution needs to explicitly handle these scenarios.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data integrity checks. XORing data can be used to detect if a single bit has been flipped during transmission or storage.

🏦Real-world scenario 2: Identifying unique identifiers or serial numbers in large datasets. The XOR approach offers an efficient way to single out the unique element without needing to store the entire dataset in memory.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Single Number"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether bit manipulation techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?