given an array of Integers where it has each element Appears in pairs (next to each other) exept for one integer , how to find this integer?

user_11915484 0
Viewed 315

I am studying for an exam and found this question with the following solution that I didn't understand it at all. Any help on what they did and why?

I have an unsorted array where each integer in the array appears in pairs (next to each other); in this array, there is only one integer that appears without a pair; also, there can't be two pairs of the same integer next to each other!

I need to find this odd integer in the best time (best time complexity) for example, given the following array: 

8 8 5 5 3 6 6 -1 -1 7 7

the output is 3!

The code:

int FindOddOccuring(int arr[], int n) {
    int left = 0, right = n / 2; 

    while (left < right) 
    { 
       int mid = (left + right) / 2; 

       if (arr[2 * mid + 1] == arr[2 * mid]) 
          left = mid + 1; 
       else 
          right = mid; 
    } 
    return arr[2 * right]; 
}
c
2 Answers

The key of this is in the line:

if (arr[2 * mid + 1] == arr[2 * mid])

Give the fact that numbers are inserted in pairs and can only be one non-paired number, if you check for two consecutives between the two last numbers of the first half in the array and they are not equal, then your rebel number will inevitably be in the second half of the array ... Why?!: because the 'rebel' number is the one wich breaks the a[i]=a[i+1] invariant, and you are checkin always from an even position to the previous one... Is my explanation clear enough? Is it too trivial? I hope it helps!

user_74010940

The above algorithm completes in O(Log2(N)), much better than traditional scan which will be O(n)

  • Divide the array in 2, find the pair in the middle.
  • If the pain in the middle matches, it indicates the odd number is to the right
  • Else the odd number must be in the left
  • Repeat as long remaining section has more than one number.

The "trick" is to perform binary search, and be able to tell if the odd value is in the left or in the right. The test on the middle pair enable the binary search

user_120984050
Related