Single Number

Difficulty: Easy | Acceptance: 77.60% | Paid: No Topics: Array, Bit Manipulation

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.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Hash Map
• Approach 3: Math
• Approach 4: Bit Manipulation

Examples

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

Approach 1: Brute Force

Intuition Check every number against all other numbers to see if it has a duplicate. If a number does not have a duplicate, it is the single number.

Steps

• Iterate through each number in the array.
• For each number, iterate through the array again to check if there is another identical number.
• If no duplicate is found, return that number.

class Solution:
    def singleNumber(self, nums):
        for i in range(len(nums)):
            found = False
            for j in range(len(nums)):
                if i != j and nums[i] == nums[j]:
                    found = True
                    break
            if not found:
                return nums[i]
        return -1

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large inputs.

Approach 2: Hash Map

Intuition Use a hash map to count the frequency of each number. The number with a frequency of 1 is the answer.

Steps

• Initialize an empty hash map.
• Iterate through the array, incrementing the count for each number in the map.
• Iterate through the map entries and return the key where the value is 1.

class Solution:
    def singleNumber(self, nums):
        counts = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
        for num, count in counts.items():
            if count == 1:
                return num
        return -1

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Faster time complexity but requires extra space proportional to the number of unique elements.

Approach 3: Math

Intuition Since every element appears twice except for one, if we sum the set of unique numbers and multiply by 2, we get the sum of the array if all numbers appeared twice. Subtracting the actual sum of the array from this value leaves the single number. 2 * (a + b + c) - (a + a + b + b + c) = c.

Steps

• Calculate the sum of the set of unique numbers.
• Calculate the sum of the original array.
• Return 2 * unique_sum - array_sum.

class Solution:
    def singleNumber(self, nums):
        return 2 * sum(set(nums)) - sum(nums)

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Elegant solution, but still uses O(n) space to store the set.

Approach 4: Bit Manipulation

Intuition XOR operation has the following properties:

• a ^ a = 0
• a ^ 0 = a
• XOR is commutative and associative. If we XOR all numbers in the array, pairs will cancel each other out (result to 0), and the single number will remain.

Steps

• Initialize a variable result to 0.
• Iterate through the array and update result by XOR-ing it with the current number.
• Return result.

class Solution:
    def singleNumber(self, nums):
        res = 0
        for num in nums:
            res ^= num
        return res

Complexity

• Time: O(n)
• Space: O(1)
• Notes: The optimal solution, meeting the linear time and constant space requirements.