# Short, compare nums[i] with nums[i^1]

• Simply find the first index whose "partner index" (the index xor 1) holds a different value.

Ruby:

``````def single_non_duplicate(nums)
nums[(0..nums.size).bsearch { |i| nums[i] != nums[i^1] }]
end
``````

Python

``````def singleNonDuplicate(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] == nums[mid ^ 1]:
lo = mid + 1
else:
hi = mid
return nums[lo]
``````

Java:

``````public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] == nums[mid ^ 1])
lo = mid + 1;
else
hi = mid;
}
return nums[lo];
}``````

• What is the meaning of partner index? Why is it useful here? Thx

• @chamberlian1990 , if mid is even, add 1 to make it odd, or if it is odd, decrease it by one.

[1,1,2,2,3].. then our mid = 2 (index 2 not value). Then we need to check for index 3 which is (10 ^ 1)b.
if our mid was index 3, then doing 3 = (11) ^ 1 = 10b = 2;

• @chamberlian1990 every 2 numbers are partner. (even,odd), (even,odd).
If mid is even, it's partner is next odd, if mid is odd, it's partner is previous even.

• ``````#include<bits/stdc++.h>
using namespace std;

int main()
{
int a[2]={0},res=0;
while(cin>>a[0] && cin>>a[1])
{
if(a[0]!=a[1])
{res=a[0];}

}
cout<<res;
return 0;
}

``````

can this be solution in c++?

• @StefanPochmann

how do you determine to move lo to mid +1 if partners are equal and if not, move hi to mid.

What is the logical reasoning behind that ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.