We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Single Number

Difficulty: Easy

Problem Description

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Key Insights

The problem requires identifying a unique element in an array where every other element appears twice.
A linear time complexity solution is required, meaning the algorithm needs to run in O(n) time.
The solution must use constant space, which implies that we cannot use additional data structures that scale with input size.

Space and Time Complexity

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

Solution

To solve this problem, we can utilize the properties of the XOR bitwise operator. The key insights are:

XOR of a number with itself is 0 (e.g., a ^ a = 0).
XOR of a number with 0 is the number itself (e.g., a ^ 0 = a).
XOR is both commutative and associative, meaning the order of operations does not affect the outcome.

By applying XOR across all elements in the array, the pairs will cancel each other out, leaving only the unique element.

Code Solutions

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num  # Apply XOR
    return result  # Return the unique number

← Back to All Questions