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 II

Number: 137

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, Google, Meta, Microsoft, Adobe, Yahoo, Apple

Problem Description

Given an integer array nums where every element appears three times except for one which appears exactly once, find and return that single element. The solution must run in linear time and utilize constant extra space.

Key Insights

  • Use bit manipulation to solve the problem in O(n) time with O(1) extra space.
  • The core idea is to track the bit counts across all numbers and use modulo operations to cancel out bits that appear three times.
  • Instead of using extra arrays for bit counts, maintain two accumulator variables to represent bits seen once and twice.
  • Leverage bitwise XOR, AND, and NOT operations to update and clear bits accordingly.

Space and Time Complexity

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

Solution

The approach uses two accumulators, named ones and twos, to track the bits that have appeared once and twice, respectively. For each number in the array, we update these accumulators:

  1. Calculate new values for ones by XOR-ing with the current number and removing any bits that are already in twos.
  2. Update twos accordingly using bits that appear and are not newly reintroduced into ones. After processing all numbers, the variable ones will contain the unique single number because the bits corresponding to numbers that appear three times cancel out.

Code Solutions

# Python solution for Single Number II
def singleNumber(nums):
    # Variables to store bits seen once and twice
    ones = 0
    twos = 0
    # Process each number in the input list
    for num in nums:
        # Update ones with the current number and clear bits already in twos
        new_ones = (ones ^ num) & ~twos
        # Update twos with the current number and clear bits just added to new_ones
        new_twos = (twos ^ num) & ~new_ones
        ones, twos = new_ones, new_twos
    return ones

# Example usage:
print(singleNumber([2,2,3,2]))  # Output: 3
← Back to All Questions