Single Number II

# Problem

problem at: https://www.lintcode.com/problem/single-number-ii

# Solution

First 3 solutions below are from LeetCode solution.

# HashSet

Convert an input array into HashSet and then to compare the tripled sum of the set with the array sum:

Complexity:

  • time:
  • space:
def singleNumber(self, nums):
    return (3 * sum(set(nums)) - sum(nums)) // 2

# HashMap

from collections import Counter
def singleNumber(self, nums):
    hashmap = Counter(nums)

    for k in hashmap.keys():
        if hashmap[k] == 1:
            return k

# Follow Up

Can you solve it using constant space?

We then have to use some clever bit manipulation methods. Both methods below take linear time and constant space.

# Digital Logic

A good explanation on the following code using digital logic.

def singleNumber(self, nums: List[int]) -> int:
    seen_once = seen_twice = 0

    for num in nums:
        seen_once = ~seen_twice & (seen_once ^ num)
        seen_twice = ~seen_once & (seen_twice ^ num)

    return seen_once

# Count Occurrences

If x is the single number result to return, then the bits where x are 1 occur 3y+1 times, where . The same case happens for 0 bits of x but doesn't make a difference on res so neglected.

Note that the highlighted line is used in place of the line below for other languages, due to Python's unbound int.

# Extension

This method can take more than 3 odd duplicates and return single number res.









 


def singleNumber(self, nums: List[int]) -> int:
    res = 0
    for i in range(32):
        cnt = 0
        for j in range(len(nums)):
            if nums[j] & (1 << i) != 0:
                cnt += 1
        res = res | ((cnt % 3) << i)
    # return res
    return res if res in nums else res - 2**32