136. Single Number

Easy

ArrayBit Manipulation

Answered: May 2, 2026

View on LeetCode

Problem Description

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

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.

💡 Hints (1)

Solutions

Complexity Analysis

Time Complexity:

O (n^{2})

We have a nested loop: for each of the $n$ elements, we scan up to $n$ others, giving $O(n^{2})$ total comparisons.

Space Complexity:

O (1)

Only a constant number of variables (found, i, j) are used regardless of input size.

This brute-force approach checks each element to see whether any other element in the array shares its value. For each index i, we scan all other indices j; if no match is found, that element has no duplicate and must be the single number. While correct, this requires comparing every element against every other, which is inefficient for large inputs.

Complexity Analysis

Time Complexity:

O (n)

Building the set and computing both sums each require a single pass over the input, so the overall time is $O(n)$ .

Space Complexity:

O (n)

The set stores up to $\lfloor n/2 \rfloor + 1$ unique elements, which is $O(n)$ in the worst case.

This approach exploits a mathematical identity: if every number appeared exactly twice, the sum of the array would equal twice the sum of its unique values. Since one number appears only once, computing 2 * sum(unique_values) - sum(all_values) cancels out all pairs and isolates the single number. We build a set to deduplicate, then compute both sums in a single linear pass each.

Complexity Analysis

Time Complexity:

O (n)

We make a single pass through the array, and each set add/remove/has operation is $O(1)$ on average, giving $O(n)$ total.

Space Complexity:

O (n)

The set holds at most $\lfloor n/2 \rfloor + 1$ elements simultaneously, so space is $O(n)$ .

This approach uses a set as a toggle: the first time we encounter a number we add it to seen, and the second time we remove it. Since every number except one appears exactly twice, paired numbers are added and then removed, leaving only the single number in the set at the end.

Complexity Analysis

Time Complexity:

O (n lo g n)

The sort dominates the runtime at $O(n \log n)$ ; the subsequent linear scan is $O(n)$ and does not change the overall complexity.

Space Complexity:

O (1)

Sorting is done in-place with no auxiliary data structures needed.

By sorting the array, all duplicate pairs become adjacent. We then step through the sorted array two elements at a time; if a pair doesn't match, the current element is the single number. If no mismatch is found during the loop, the single number must be the last element, which had no pair to sit beside.

Complexity Analysis

Time Complexity:

O (n)

We make a single pass through the array performing one XOR operation per element, so the time complexity is $O(n)$ .

Space Complexity:

O (1)

Only a single result variable is needed regardless of input size.

This approach leverages two key XOR properties: any number XORed with itself equals 0, and any number XORed with 0 equals itself. By XORing all elements together, every number that appears twice cancels out to 0, and only the single unpaired number remains as the final result.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$	No extra space needed	Quadratic time makes it impractical for large inputs
Math	$O(n)$	$O(n)$	Intuitive mathematical identity	Requires $O(n)$ extra space for the set
Toggle Set	$O(n)$	$O(n)$	Clean, readable toggle logic	Requires $O(n)$ extra space for the set
Sorting	$O(n \log n)$	$O(1)$	Constant space with no extra data structures	Superlinear time due to sorting
XOR Bit Manipulation	$O(n)$	$O(1)$	Optimal time and space; elegantly leverages XOR properties	Requires familiarity with bitwise operations

The optimal approach for this problem is Solution 5: XOR Bit Manipulation, which achieves $O(n)$ time complexity and $O(1)$ space complexity. By XORing all elements together, every paired duplicate cancels out to zero, leaving only the single unpaired number with no extra memory required.

Solutions

lines
1class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      # Iterate through each number in the list and check if it appears more than once.
      for i in range(len(nums)):
          found = False # Flag to indicate if a duplicate is found
6
          # Check if the current number appears more than once in the list.
          for j in range(len(nums)):
              if i != j and nums[i] == nums[j]:
                  found = True
                  break
12
          if not found: # If no duplicate is found, return the current number as the single number.
              return nums[i]

Complexity Analysis

Time Complexity:

O (n^{2})

We have a nested loop: for each of the $n$ elements, we scan up to $n$ others, giving $O(n^{2})$ total comparisons.

Space Complexity:

O (1)

Only a constant number of variables (found, i, j) are used regardless of input size.

lines
1class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      set_nums = set(nums)
4
      # Calculate the sum of the unique numbers and the sum of all numbers.
      sum_set = sum(set_nums)
      sum_nums = sum(nums)
8
      # The single number is the difference between twice the sum of the unique numbers and the sum of all numbers.
      return 2 * sum_set - sum_nums

Complexity Analysis

Time Complexity:

O (n)

Building the set and computing both sums each require a single pass over the input, so the overall time is $O(n)$ .

Space Complexity:

O (n)

The set stores up to $\lfloor n/2 \rfloor + 1$ unique elements, which is $O(n)$ in the worst case.

lines
1class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      # Using a set to track seen numbers. If a number is seen again, it is removed from the set.
      seen = set()
5
      for num in nums:
          if num in seen: # If the number is already in the set, it means we've seen it before, so we remove it.
              seen.remove(num)
          else: # If the number is not in the set, we add it to the set.
              seen.add(num)
11
      # The single number will be the only element left in the set.
      return seen.pop()

Complexity Analysis

Time Complexity:

O (n)

We make a single pass through the array, and each set add/remove/has operation is $O(1)$ on average, giving $O(n)$ total.

Space Complexity:

O (n)

The set holds at most $\lfloor n/2 \rfloor + 1$ elements simultaneously, so space is $O(n)$ .

lines
1class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      # Sort the array to bring duplicates together
      nums.sort()
5
      # Iterate through the sorted array and check for pairs
      for i in range(0, len(nums) - 1, 2):
          if nums[i] != nums[i + 1]:
              return nums[i]
10
      # If the single number is the last element in the sorted array
      return nums[-1]

Complexity Analysis

Time Complexity:

O (n lo g n)

The sort dominates the runtime at $O(n \log n)$ ; the subsequent linear scan is $O(n)$ and does not change the overall complexity.

Space Complexity:

O (1)

Sorting is done in-place with no auxiliary data structures needed.

lines
1class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      # XOR of a number with itself is 0, and XOR of a number with 0 is the number itself.
      result = 0
5
      for num in nums:
          result ^= num
8
      return result

Complexity Analysis

Time Complexity:

O (n)

We make a single pass through the array performing one XOR operation per element, so the time complexity is $O(n)$ .

Space Complexity:

O (1)

Only a single result variable is needed regardless of input size.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$	No extra space needed	Quadratic time makes it impractical for large inputs
Math	$O(n)$	$O(n)$	Intuitive mathematical identity	Requires $O(n)$ extra space for the set
Toggle Set	$O(n)$	$O(n)$	Clean, readable toggle logic	Requires $O(n)$ extra space for the set
Sorting	$O(n \log n)$	$O(1)$	Constant space with no extra data structures	Superlinear time due to sorting
XOR Bit Manipulation	$O(n)$	$O(1)$	Optimal time and space; elegantly leverages XOR properties	Requires familiarity with bitwise operations

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

💡 Hints (1)

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Math

Complexity Analysis

Explanation

Solution 3: Toggle Set

Complexity Analysis

Explanation

Solution 4: Sorting

Complexity Analysis

Explanation

Solution 5: XOR Bit Manipulation

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

💡 Hints (1)

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Math

Complexity Analysis

Explanation

Solution 3: Toggle Set

Complexity Analysis

Explanation

Solution 4: Sorting

Complexity Analysis

Explanation

Solution 5: XOR Bit Manipulation

Complexity Analysis

Explanation

Conclusion