Iam_Sandeep

Two numbers with odd occurences

Jul 29th, 2022 (edited)
823
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.95 KB | None | 0 0
  1. #User function Template for python3
  2. #To extract lsb do lsb=a&-a or lsb =a&~(a-1)
  3. #To unset last set bit do a=a&(a-1)
  4. '''
  5. 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.
  6. '''
  7. class Solution:
  8.     def twoOddNum(self, a, n):
  9.         xor=0
  10.         for i in a:
  11.             xor = xor^i
  12.         #Remove find out right most set bit because this will separate out into (0,1) grps since 0 xor 1= 1 xor 0
  13.         #Now i will make all numbers into two groups bases on rsb
  14.         #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
  15.         rsb = xor & (-xor)
  16.         x,y=0,0
  17.         for i in a:
  18.             if rsb&i==0:
  19.                 x=x^i
  20.             else:
  21.                 y=y^i
  22.         return [y,x] if x<y else [x,y]
Advertisement
Add Comment
Please, Sign In to add comment