Quite a few problems on Leetcode utilized bitwise operators, especially for those Single Number problem series like this one:
260 . Single Number III
Difficulty: Medium
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5]
return [3, 5]
Note:
The order of the result is not important. So in the above example, [5, 3]
is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
The answer I submitted is:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
xor = 0
for num in nums:
xor ^= num
musk = 1
while (xor&musk == 0):
musk = musk << 1
a=0
b=0
for num in nums:
if num&musk:
a ^= num
return [a,a^xor]
Before it was accepted, the "time limit exceeded" warning kept pop out. After searching online, I found my answer differs with accepted answer only in the part musk = musk<<1, where in my previous answer it was musk<<1. Testing musk<<1 in Canopy Python distribution reveals that value of musk didn't change at all. Correct representation should be musk<<=1, as analogical to count += 1. I guess to eliminate confusion, musk<<1 is not accepted in Python just like i++ not accepted neither.
