# Lonely Integer

# Lonely Integer

+ 23 comments Python's awesome

answer = reduce((lambda x, y: x^y), a)

+ 9 comments ### Java solution - passes 100% of test cases

O(n) runtime. O(1) space. Uses XOR. Keep in mind:

- x ^ x = 0
- x ^ 0 = x
- XOR is commutative and associative

public static int lonelyInteger(int [] array) { int val = 0; for (int num : array) { val = val ^ num; // ^ is XOR operator } return val; }

From my HackerRank Java solutions.

+ 3 comments Whoa, this XOR solution was really an eye-opener to me. Before this, I always programmed stuff "inside a box". Now I know I can (and I will try harder to) connect everything I've learned - mathematics, computer science, digital logic etc.

+ 5 comments I have a O(n) solution but I need to use a set so the space complexity is O(n). I think the optimal solution requires bit manipulation? can you provide that?

+ 0 comments Here's my JavaScript solution after seeing daniel's explaination:

`function lonelyinteger(a) { return a.reduce((a, b) => a ^ b) }`

Quote from Daniel C

I learn better with examples, so here I go trying to explain to my future self.

Let's say we have an array with: [1, 2, 2, 3, 1] We, know just by eyeballing it, the lonely integer is: 3 but we want to solve it using bit manipulation.

Just for notes: bit for 1=001, for 2=010, for 3=011 to get the answer, we just simply XOR all the values, and the remainder would be the lonely integer. since if the same number is being XOR with that same number, it will get 0.

back to example: first xor: 1^2 = 001^010 = 011 = 3 second xor (using the value from first xor): 3^2 = 011^010 = 001 = 1 third xor (using the value from previous xor): 1^3 = 001^011 = 010 = 2 last xor (using the value from previous xor): 2^1 = 010^001 = 011 = 3

that's how we get the answer 3.

Sort 475 Discussions, By:

Please Login in order to post a comment