Advertisement
Iam_Sandeep

Two Repeated Elements

Jul 29th, 2022 (edited)
561
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.64 KB | None | 0 0
  1. '''
  2. You are given an array of N+2 integer elements. All elements of the array are in range 1 to N. Also, all elements occur once except two numbers which occur twice. Find the two repeating numbers.
  3. '''
  4. # Python3 code to Find the
  5. # two repeating elements
  6. # in a given array
  7. def printRepeating(arr, size):
  8.    
  9.     # Will hold xor
  10.     # of all elements
  11.     xor = arr[0]
  12.     n = size - 2
  13.     x = 0
  14.     y = 0
  15.    
  16.     # Get the xor of all
  17.     # elements in arr[]
  18.     # and 1, 2 .. n
  19.     for i in range(1 , size):
  20.         xor ^= arr[i]
  21.     for i in range(1 , n + 1):
  22.         xor ^= i
  23.    
  24.     # Get the rightmost set
  25.     # bit in set_bit_no
  26.     set_bit_no = xor & ~(xor-1)
  27.    
  28.     # Now divide elements in two
  29.     # sets by comparing rightmost
  30.     # set bit of xor with bit at
  31.     # same position in each element.
  32.     for i in range(0, size):
  33.        
  34.         if(arr[i] & set_bit_no):
  35.            
  36.             # XOR of first
  37.             # set in arr[]
  38.             x = x ^ arr[i]
  39.         else:
  40.            
  41.             # XOR of second
  42.             # set in arr[]
  43.             y = y ^ arr[i]
  44.            
  45.     for i in range(1 , n + 1):
  46.  
  47.         if(i & set_bit_no):
  48.            
  49.             # XOR of first set
  50.             # in arr[] and
  51.             # 1, 2, ...n
  52.             x = x ^ i
  53.         else:
  54.            
  55.              # XOR of second set
  56.              # in arr[] and
  57.              # 1, 2, ...n
  58.             y = y ^ i
  59.            
  60.     print("The two repeating",
  61.          "elements are", y, x)
  62.  
  63. # Driver code    
  64. arr = [4, 2, 4,
  65.        5, 2, 3, 1]
  66. arr_size = len(arr)
  67. printRepeating(arr, arr_size)
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement