Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
The description was taken from https://leetcode.com/problems/single-number-ii/.
#Hashmap Solution#O(N) Time, O(N) Spaceclass Solution: def singleNumber(self, nums: List[int]) -> int: seen = {} for num in nums: if num in seen: seen[num] += 1 else: seen[num] = 1 for num in seen: if seen[num] == 1: return num#Hashset Solution#O(N) Time, O(N) Spaceclass Solution: def singleNumber(self, nums: List[int]) -> int: return (3 * sum(set(nums)) - sum(nums)) // 2#Binary Solution#O(N) Time, O(1) Spaceclass Solution: 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_onceThe same linear space solution from the first variation of this problem can also be utilized to solve this version.
Let's initialize a dictionary to count the number of times we have seen each number.
seen = {}
For each number in the array, if we have already seen the number, then we will increment its frequency in our dictionary. if not, we will initialize it there with a value of one.
for num in nums: if num in seen: seen[num] += 1 else: seen[num] = 1
Once we have each number and a count of their occurrence in our dictionary, we will traverse the array once more and return the number with a single occurrence.
for num in seen: if seen[num] == 1: return num
In this variation of the problem, each number appears three times instead of twice like it was in the last variation. That means we can apply a similar mathematical HashSet approach. If we were to multiply each unique number by three and then subtract them by the list of numbers, all of the numbers that appear three times would become zero. The number that appeared once would have been multiplied by three but only subtracted by itself once, leaving two more instances of the number. If we were to divide the sum of those instances by two, we would isolate the number.
return (3 * sum(set(nums)) - sum(nums)) // 2
An example of this would be [2,2,3,2].
((3 * sum(set(nums))) – sum(nums))/2
= ((3*(5)) - 9) /2
= (15 – 9)/2
= 6/2
= 3
This problem can also be solved with bit manipulation using NOT, AND, and XOR gates.
Similar to the HashSet approach, the overall picture is that the numbers that appear three times will cancel out to zero, leaving only the number that appears once. This is the same idea as the binary solution to the first Single Number problem but it is much more difficult to implement with the nonunique numbers appearing three times instead of two.
We will do this using these variables that keep track of how many times we have seen the number.
seen_once = seen_twice = 0
If the number we're looking for is not seen twice, AND seen once is not the current number, we will keep it in seen once.
for num in nums: seen_once = ~seen_twice & (seen_once ^ num)
If the number we're looking for is not in seen once, AND seen twice is also not the current number, we will keep it in seen twice.
seen_twice = ~seen_once & (seen_twice ^ num)
Let's draw this out with the example, [2,2,2,3].
This is the truth table for an XOR gate:
x XOR x = 0
x XOR 0 = x
During our traversal, once we arrive at the third instance of two, we will have:
| current | =2 |
| seen_once | =0 |
| seen_twice | =2 |
seen_once = (NOT 2) AND (0 XOR 2)
= 0
All the numbers that appear three times will become zero, as shown in the previous step.
When we get to the number that appears once, the three, we will have:
| current | =3 |
| seen_once | =0 |
| seen_twice | =0 |
seen_once = (NOT 0) AND (0 XOR 3)
= 3
return seen_once