Single Number - Leetcode 136 - Python

0:00 - Read the problem
0:38 - O(n) Memory Solution
1:25 - O(1) Memory Solution
6:16 - Coding Solution

leetcode 136

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[blairbass]

One huge point that is missing from this explanation that may help others (like myself) who were previously unfamiliar with XOR: the XOR operation is associative and commutative. That means a ^ (b ^ c) = (a ^ b) ^ c, and a ^ b = b ^ a. From these two properties, we can see that ((((4 ^ 1 ) ^ 2 ) ^ 1 ) ^ 2 ) = (2 ^ 2) ^ (1 ^ 1) ^ 4. The left hand side of this equation is what the solution code is effectively doing. On the right hand side, we can take the basic XOR operation principles discussed in the video to see that it equals 0 ^ 0 ^ 4 = 0 ^ 4. Since n ^ 0 = n, then we know that the answer is 4.

[CostaKazistov]

Simply brilliant!
This is the best channel for LeetCode walkthroughs on YouTube.
The way you explain how to develop intuition for this problem is truly next level.

[DanhWasHere]

Another example of a "Crackhead" problem as NeetCode described before -like the video says and the comments say, only people who encountered this problem would think to XOR first.

[jason]

I wonder if anyone ever intuits this solution out. Seems like a good way to make sure you only pass people who've memorized this solution

[tahaansari]

Thanks! I was looking for the xor solution.

[expansivegymnast]

Thank you! This is why I'm going through the LeetCode Easy's I still learn things

[licokr]

I've tried to understand it by myself but I didn't ensure 100%. Organzize all bits and even one bits will be zero and there ends up the number exists once. That's the simplest explanation I could imagine. Thank you so much!

[fethanus]

The key point is XOR operation is ASSOCIATIVE. This means
A ^ B ^ C = C ^ A ^ B so if two operants are same result will be 0.
0 ^ singleNumber = singleNumber. So we result variable initialized 0

[kirillzlobin]

Amazing, but.... how do you come up to this solutions...?

[nikhilgoyal]

thanks! sorry for the basic question but how does the code know that for res = n ^ res, n needs to be changed to binary for this operation ? thanks!

[venkatrushivanga]

Never thought like this it can be solved. Good bro🙂

[LoganLi-suju]

I come up with this solution by myself！ I am clever😁

[Deschuttes]

Is this just something you learn in CS classes? I write frontend and never ran into needing to use XOR. I mean, I was aware of its existence.

[dustinscroggins]

I sorted the numbers then compared pairs !! Would that fit the conditions for the time complexity?

[grandparick]

Man I solved this problem using sorting and hashmap but I just couldn't optimize it any further no matter what. I didn't even knew about this method.

[marekglowacki]

ultra fast and memory lean one-liner: reduce(xor, nums), reduce from functools, xor from operator

[rodgerdodger]

I was asked this for amazon and completely failed. Went over the problem in my DSA class 4 days later...

[zoabdullah]

i solved it like this:

for index in range(len(nums)):
if nums.count(nums[index])==1:
return nums[index]

[JonathanJoaquinQuirinoCarrasco]

Wow, very interesting solution man, my solution is the following: def singleNumber(self, nums: List[int]) -> int:

hash_map = {}

for num in nums:
hash_map[num] = 1 + hash_map.get(num, 0)

for n in hash_map:
if hash_map.get(n, 0) == 1:
return n

[Alexthesurfer]

return reduce(lambda a, b: a ^ b, nums)