LeetCode Single Number Solution Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[phungtruong]

This is the first time i use XOR when coding. It's easy, thank you Nick

[NicoleVardo]

Not stupid at all! I really like this explanation with xor Better than the hashmaps. Thank you

[jankidepala]

Its been 4 hours I am trying to figure out XOR...Thanks :)

[Gideon_Judges]

Keep in mind that this solution only works if you have even numbers of duplicates (e.g. pairs as in the problem statement). As soon as you have odd number of duplicates it fails. Note that XOR is the binary operator of the more general n-ary odd function.

[fedest]

Here’s my explanation on why it works, regardless of the order of the numbers:
Keep in mind that for any bit A, you have A^0 == A, and A^1 != A, or said differently, xor’ing with a 1 “flips” its value, and xor’ing with a 0 leaves it unchanged.

Now consider each individual bit position in the int result. As you traverse the array, you’ll see ints having either a 0 or 1 in that position. The total number of 1s seen for that position, indicates how many times the bit at that position in result is flipped. Of course, for duplicate numbers, you’ll see the same bit twice, and flipping a bit twice (or any even number of times) is the same as leaving it unchanged.
Since result starts with all the bits as 0, in the end the value for the bit at each position will be 1 iff the total number of 1s at that position is odd, and that can only happen if the unique number in the array has a 1 at that bit position. Therefore, all bits in result will have the same value as the bits in the unique number, so they are the same number.

[jay-cover]

a good way to think of this is that there's only one distinct element in the list, every other pair of duplicate elements are going to be 0 if doing the XOR operation. so the whole for loop is basically reduced to just doing one XOR operation, which is 0 XOR that distinct element. And that is why the initial value set to 0.

[jeffery]

you can show with this: 0^2^2, basically xor twice it's back to 0

[treyquattro]

nicely explained. Any number XOR'd with itself is zero. Any number XOR'd with zero is the number itself. It really helps to know binary representations of numbers, and also assembler-level programming (although not strictly necessary) :)

[nihak]

Explanations helps breaking down the cloud of confusions thanks to you! :)

[olenaqwerty]

thanks for the video. you are the only person on youtube with so many leet code problem solutions

[harinijeyaraman]

Love your videos man ! Good and concise explanations !

[saketpanchori]

To understand XOR just convert numbers into base 2(0 and 1) then try you will get the unique number always

[yergalemteferi]

You did a good explanation and it is very clear thanks

[mashak]

thank you for your explanation - really helpful!

[sol]

I don't know why first solution uses less memory...

[jeezradz]

thanks for the explanation!! not stupid at all.

[rishabhjain]

Anything stupid enough to solve this question is not stupid at all !

[thanGamer]

can somebody explain what the ^= operator does?