We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Lonely Integer
- Discussions
Lonely Integer
Lonely Integer
Sort by
recency
|
212 Discussions
|
Please Login in order to post a comment
Python:
Hey folks,
My solution in javascript with time complexity Big O of n,
}
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.