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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Single Number

Number: 136

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, Meta, Bloomberg, tcs, Accenture, Apple, Adobe, Yandex, Zoho, Uber, Yahoo, Airbnb, Palantir Technologies

Problem Description

Given a non-empty array of integers where every element appears twice except for one, find the unique element that appears only once.

Key Insights

  • Using bitwise XOR: XOR-ing a number with itself cancels out to 0.
  • XOR is both commutative and associative, so the order of operations does not matter.
  • A single traversal (linear time) and constant extra space is sufficient for solving the problem.

Space and Time Complexity

Time Complexity: O(n) – We only traverse the array once. Space Complexity: O(1) – Only a single extra variable is used regardless of input size.

Solution

We can solve this problem by initializing a variable to 0 and then traversing the array while XOR-ing each element with the variable. Due to the properties of XOR, pairs of identical numbers will cancel each other out (x XOR x = 0) and the unique number will be left as the final result. This approach uses constant extra space and performs in linear time.

Code Solutions

# Function to find the single number in the list
def singleNumber(nums):
    # Initialize result to 0; any number XOR 0 is the number itself
    result = 0
    # Iterate through every number in the list
    for num in nums:
        # XOR the current result with the current number
        result ^= num  # Using XOR to cancel duplicates
    # Return the unique number that did not cancel out
    return result

# Example usage
nums = [4, 1, 2, 1, 2]
print(singleNumber(nums))  # Output should be 4
← Back to All Questions