Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #User function Template for python3
- #To extract lsb do lsb=a&-a or lsb =a&~(a-1)
- #To unset last set bit do a=a&(a-1)
- '''
- Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.
- '''
- class Solution:
- def twoOddNum(self, a, n):
- xor=0
- for i in a:
- xor = xor^i
- #Remove find out right most set bit because this will separate out into (0,1) grps since 0 xor 1= 1 xor 0
- #Now i will make all numbers into two groups bases on rsb
- #Then we caluculate xor of these two groups. If even pairs are there they cancel out in grpxor sum remaining left with the ones which are odd in count
- rsb = xor & (-xor)
- x,y=0,0
- for i in a:
- if rsb&i==0:
- x=x^i
- else:
- y=y^i
- return [y,x] if x<y else [x,y]
Advertisement
Add Comment
Please, Sign In to add comment