Single Number | Leetcode 136 | Brute Force and Optimal solution in Python

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.

Here’s the [Problem Link] to begin with.

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.

Solution 1: Brute Force Approach (Using Hash Map)

Intuition

Imagine you’re counting how many times each person shows up at a party! If most people come in pairs but one person comes alone, you want to find that lone person. The simplest way is to keep a tally – count how many times each number appears in the array. Then, look through your tally and find the number that appears only once. That’s our answer!

Detailed Approach

1. Create a Hash Map: Use a dictionary to store the frequency of each number.
2. Count Frequencies: Loop through the array and increment the count for each number in the hash map.
3. Find Single Occurrence: Loop through the hash map to find the number with a frequency of 1.
4. Return the Result: Return the number that appears only once.

Code

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        hash_map = dict()
        # First pass: Count frequency of each number
        for i in range(n):
            hash_map[nums[i]] = hash_map.get(nums[i], 0) + 1
        
        # Second pass: Find the number with frequency 1
        for k in hash_map:
            if hash_map[k] == 1:
                return k

Code Explanation

We use a dictionary (hash_map) to keep track of how many times each number appears in the array. The get method helps us safely increment the count even for numbers not yet in the map (defaulting to 0). After counting, we iterate through the dictionary’s keys and return the first (and only) number that has a frequency of 1. This works because the problem guarantees there is exactly one number that appears once, while all others appear twice.

Dry Run

Let’s trace through: nums = [1][1]

First Pass (Count Frequencies):

• num=4: hash_map = {4: 1}
• num=1: hash_map = {4: 1, 1: 1}
• num=2: hash_map = {4: 1, 1: 1, 2: 1}
• num=1: hash_map = {4: 1, 1: 2, 2: 1}
• num=2: hash_map = {4: 1, 1: 2, 2: 2}

Second Pass (Find Single):

• key=4, freq=1 → return 4

Result: 4

Time and Space Complexity

• Time Complexity: O(n) – We traverse the array once to build the hash map and then traverse the map (which has at most n/2 + 1 entries)
• Space Complexity: O(n) – We store up to n/2 + 1 entries in the hash map

Simplifying It

This approach is like making a checklist of everyone at a party and counting how many times each name appears. You go through your list once to count, and then check who shows up only once. It’s straightforward but uses extra space to store the counts.

Solution 2: Optimal Approach (Bitwise XOR)

Intuition

Imagine you’re at a magic show where pairs of identical items disappear when put together! The XOR operation is like that magic trick – when you XOR two identical numbers, they cancel out to 0. Since every number except one appears twice in our array, if we XOR all numbers together, the pairs will cancel out (become 0), and the only number left will be the one that appears once. It’s pure magic with bits!

Detailed Approach

1. Initialize Result: Start with a result variable set to 0.
2. XOR All Numbers: Loop through the array and XOR each number with the result.
3. Pairs Cancel Out: Every number that appears twice will cancel out (XOR of a number with itself is 0).
4. Single Remains: The final result will be the number that appears only once.
5. Return the Result: Return the final XOR value.

Code

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        # XOR all numbers in the array
        for i in range(0, len(nums)):
            ans = ans ^ nums[i]
        return ans

Code Explanation

We use the XOR operation (^) which has some amazing properties:

• XOR of a number with itself is 0 (e.g., 2 ^ 2 = 0)
• XOR of a number with 0 is the number itself (e.g., 2 ^ 0 = 2)
• XOR is associative and commutative (order doesn’t matter)

Since every number except one appears twice, XORing all numbers will cancel out the pairs (resulting in 0 for each pair), and the only remaining value will be the single number. This approach is incredibly efficient as it requires only one pass and no extra space.

Dry Run

Let’s trace through: nums = [1][1]

Step-by-Step XOR:

• ans = 0
• ans = 0 ^ 4 = 4
• ans = 4 ^ 1 = 5
• ans = 5 ^ 2 = 7
• ans = 7 ^ 1 = 6
• ans = 6 ^ 2 = 4

Result: 4

How it works under the hood (binary):

• 4 = 0100
• 1 = 0001
• 2 = 0010
• Step 1: 0000 ^ 0100 = 0100 (4)
• Step 2: 0100 ^ 0001 = 0101 (5)
• Step 3: 0101 ^ 0010 = 0111 (7)
• Step 4: 0111 ^ 0001 = 0110 (6) // 1 cancels with 1
• Step 5: 0110 ^ 0010 = 0100 (4) // 2 cancels with 2

Result: 4 (the single number)

Time and Space Complexity

• Time Complexity: O(n) – We traverse the array once
• Space Complexity: O(1) – We only use a single variable regardless of input size

Simplifying It

This approach is like a magic trick where pairs of identical cards disappear when you stack them. You go through the deck once, pairing up matching cards (XOR cancels them to 0), and at the end, the only card left in your hand is the unique one. No extra space needed, just one pass through the deck!

Summary

The optimal XOR approach is generally preferred because it meets the problem’s constraints of linear time and constant space. The brute force hash map approach is more intuitive and easier to understand when you’re first learning, but it uses extra space which isn’t ideal for this problem.

The XOR solution is a beautiful demonstration of how bitwise operations can solve problems efficiently. It’s a classic interview question that showcases the power of understanding fundamental computer science concepts like XOR properties. If you’re preparing for coding interviews, mastering this trick is a must as it appears in various forms in other problems too!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.