You are viewing a single comment's thread. Return to all comments →
C Implementation:
int lonelyinteger(int a_count, int* a) { int unique = 0; for(int i =0; i<a_count; i++) { unique ^= a[i]; } return unique; }
Explanation:
XOR properties:
Identity: a⊕0 = a
Self-Cancellation: a⊕a =0
Commutative: a⊕b = b⊕a
Associative: a⊕(b⊕c) = (a⊕b)⊕c
Let's denote the array as [x1,x2,...,xn] where every element xi appears exactly twice except for one unique element u.
Let's denote the XOR operation applied to all elements of the array as R.
R=x1⊕x2⊕...⊕xn
According the properties of XOR, we can group the elements that appear twice and simplify:
R = (a⊕a)⊕(b⊕b) ⊕(u)
Here, XORing all elements in the array will cancel out all duplicate elements leaving us with the unique element u.
Seems like cookies are disabled on this browser, please enable them to open this website
Lonely Integer
You are viewing a single comment's thread. Return to all comments →
C Implementation:
Explanation:
XOR properties:
Identity: a⊕0 = a
Self-Cancellation: a⊕a =0
Commutative: a⊕b = b⊕a
Associative: a⊕(b⊕c) = (a⊕b)⊕c
Let's denote the array as [x1,x2,...,xn] where every element xi appears exactly twice except for one unique element u.
Let's denote the XOR operation applied to all elements of the array as R.
R=x1⊕x2⊕...⊕xn
According the properties of XOR, we can group the elements that appear twice and simplify:
R = (a⊕a)⊕(b⊕b) ⊕(u)
Here, XORing all elements in the array will cancel out all duplicate elements leaving us with the unique element u.