Single Number - Leetcode 136 - Python
Vložit
- čas přidán 26. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Python Code: github.com/neetcode-gh/leetco...
Problem Link: neetcode.io/problems/single-n...
0:00 - Read the problem
0:38 - O(n) Memory Solution
1:25 - O(1) Memory Solution
6:16 - Coding Solution
leetcode 136
This question was identified as an amazon coding interview question from here: github.com/xizhengszhang/Leet...
#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Python Code: github.com/neetcode-gh/leetcode/blob/main/136-Single-Number.py
Java Code (from a viewer - ndesai): github.com/ndesai15/coding-java/blob/master/src/com/coding/patterns/bitwiseXOR/SingleNumberXOR.java
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.
Disagree.
I saw it for the first time and came up with XOR solution.
4 1 2 1 2
My logic was like this:
If we could sum the first three numbers:
4 + 1 + 2 = 7
And then somehow subtract the rest (duplicates):
7 - 1 - 2 = 4
We would have that unique number left.
And then I thought of XOR.
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.
cheers
Thanks, this definitely cleared it up for me.
Thanks a lot man. I have been getting crazy about the fact that the order does not matter. I have been asking myself WWWHHHYYYY !!!!
Thanks a lot, I am just about to search it!
this is the exact bit I was missing! thanks :)
Simply brilliant!
This is the best channel for LeetCode walkthroughs on CZcams.
The way you explain how to develop intuition for this problem is truly next level.
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
Perhaps they're looking for a mathematician who can also prove that the solution works xD
Yup, sometimes it’s just luck during an interview. Luck that you have seen the same or similar problem.
Similar questions and concepts are taught in basic ass firmware engineering courses because these types of operations are fast and efficient so you get into the habit of approaching every problem this way.
So I suppose the answer to your question is no unless that's who they were attempting to hire with this question. There's effectively zero chance you would ever "stumble" upon the solution thinking it out unless you are an embedded systems engineer or deal with this type of stuff on a frequent basis.
@@LiveType I've taken discrete maths, and a digital logic course just last semester, so XOR is a pretty common thing for me. And, it still didn't ever occur to me that you could xor like a hashSet to get rid of duplicate value, that's very clever.
Thanks! I was looking for the xor solution.
Thank you! This is why I'm going through the LeetCode Easy's I still learn things
A difficult concept, thanks a lot!
What a cool solution. Love it.👍
Never thought like this it can be solved. Good bro🙂
Your explanation is so good
Awesome explanation!
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!
Love you man!
What's up bro, ur videos are really helpful thanks 💯
Thank you so much!
i would never ever think about it
Thanks!
Thank you so much!!
Brilliant explanation
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!
Thank you very much
Would you consider doing fair indexes Leetcode 1882?
If the unique number is at the end of the array I am getting 0 as the return value. Will have to think of a solution that covers that unless I am missing something here?
ultra fast and memory lean one-liner: reduce(xor, nums) , reduce from functools, xor from operator
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.
Same here 😰
Thanks
I come up with this solution by myself！ I am clever😁
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
Amazing, but.... how do you come up to this solutions...?
Thanx
I was asked this for amazon and completely failed. Went over the problem in my DSA class 4 days later...
Sorry, if only it came after you learnt it.
Could someone confirm, so basically the ^ (xor operator) looks through the entire list and checks if there is an even number of the num, and if there is, then they cancel?
i solved it like this:
for index in range(len(nums)):
if nums.count(nums[index])==1:
return nums[index]
I sorted the numbers then compared pairs !! Would that fit the conditions for the time complexity?
i think array.sort is n(logn) so i dont think so ... if that's what you used.
@@JayGrant ah okay makes sense I was just trying to find another way to solve it
@@dustinscroggins6256 i understand, this was the first solution that i thought of actually.
what if the repeated numbers were repeated n extra times instead of 2 , eg 3
result=0
for i in nums:
result ^= i
return result
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.
Yes.
If you do lower level stuff then you will need it.
frontend is all you ever need in the universe /s
Is this technically O(1) space? The size of the result variable doesn't scale with the length of the input list, but it does scale with the size of the numbers in the input list.
the number of bits allocated for an integer does not change, and even if it did, it wold be O(max(number of bits for all elements of array)) = O(1) since the max is a constant
🔥🔥🔥🔥
Wait isn't the hashset solution O(1) , at any point of time we will only store a single element if we pop out the re-encountered element ?
The numbers aren’t in order so we might need to store more and more until we encounter the duplicates
return reduce(lambda a, b: a ^ b, nums)
return reduce(operator.xor, nums)
U a Single Number God
Could also use the sliding window algorithm and delete the duplicates as you find them ... index 0 at the end will be your single number
The problem states "You must implement a solution with a linear runtime complexity and use only constant extra space."
@@koeber99 my solution is linear and constant! not using extra space as you just delete from the array as you go, and sliding window is about linear time
@@jzimmer95 how do you know a number is a duplicate with constant space and keeping in mind the array can't be sorted (nlogn operation)?
@@jzimmer95 solution that copies the list is o(n) in extra space
take an XOR of the elements.
In the starting you mention for hashset 2 be removed completely. Shouldnt it just be one time
Why does
res = 0
for i in range(len(nums)):
res = i ^ res
return res
not work? isn't it the same thing?
your iterating through the length of the array,(0,1,2,3,4,...,n) instead of the array itself. Good luck!
The idea is that the same numbers cancel out each other, to do that we need to use XOR only with the numbers on the input array, not with counter "i". `i` could be or couldn't be in the input array.
i represents the array index not the array value. replace "res = i ^ res" with "res = nums[i] ^ res"
done
can someone explain me from 4:11
3:34 Please can someone explain this to me. Why does not the order matter ????
XOR of a number with itself is 0:
If you XOR a number with itself, the result is always 0.
For any integer a, a ^ a equals 0.
This property is crucial for canceling out pairs of identical numbers.
Example:
5 ^ 5 equals 0.
101 (binary representation of 5) ^ 101 (binary representation of 5) equals 000 (binary representation of 0).
Commutative Property of XOR:
The order in which you perform XOR operations does not affect the result.
For any integers a and b, a ^ b is equal to b ^ a.
The XOR operation is commutative.
Example:
3 ^ 5 is the same as 5 ^ 3.
Associative Property of XOR:
The grouping of XOR operations does not affect the result.
For any integers a, b, and c, (a ^ b) ^ c is equal to a ^ (b ^ c).
The XOR operation is associative.
Example:
(2 ^ 7) ^ 3 is the same as 2 ^ (7 ^ 3).
These properties make XOR a powerful tool for finding unique elements in a set. In the context of finding a single number in an array where every other number appears twice, XORing all the numbers will cancel out pairs, leaving only the unique number.
Consider an array [2, 2, 1, 4, 1]:
2 ^ 2 ^ 1 ^ 4 ^ 1 is the same as (2 ^ 2) ^ (1 ^ 4 ^ 1).
The pairs cancel out, and the result is the unique number: 0 ^ 4.
The final result is 4, which is the number that appears only once in the array.
sometimes you make solution complicated and makes to quit coding
Unfortunately, the explanation for the bit manipulation solution about 5 minutes into the video, where you try to show that the solution can be intuited without knowing that XOR is commutative, is wrong. The reason is that it assumes that the unique number is first (or last) in the list. Were the single number in the middle of the list somewhere, there could be an odd number of numbers on either side of it in the list. For example, reorder the list to [1,2,1,4,2]. In this case you would have a single one in the ones column of each group of non-unique numbers, and you'd still have to appeal to the commutative property to cancel out the ones.
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
This is giving me wrong answer. Anybody know why?
lol love this problem,
please never stop
xor ^
Theres an easier way to do this. The single number is simply: 2*sum(set(nums)) - sum(nums). One line thats faster than 99% of the solutions on leet
but sum is need too loop over all array, isn't it?
you're creating a set of sums in this case, which uses O(N) space complexity
😀😀😀
each value is index, now go to that index and make it -. if you see already the number is - then it is duplicate. if not - then it is unique.
It wouldn't work assuming there are numbers which have bigger values then the length of the index
0 xor 1 gives 1
First view first like 🤞
for ele in set(nums) :
if nums.count(ele) == 1 :
return ele
Please consider to make videos about DS and AL.. 🙏
What do you think his channel is all about?
He asked the viewers about it..and after taking viewers feedback via vote ..most of them voted against it.
And y is that?...because it takes time for it and he have to dedicate energy and time just for it, which inturn drastically reduces frequency of neetcode videos
Since DS and al is all over the youtube and with just some little more research you can find some wonderful yt channels teaching those.
But for neetcode ..this is only channel we can blindly depend on!
hi there, in case if someone doesn't understand so here will be another way:
a = set{nums}
return 2*sum(a) - sum(nums)
this way is very easy to understand.
This solution does not use constant space
bit manipulation coding questions should be banned from coding interviews
let h = new Array(Math.abs(nums.length)).fill(0);
if(nums.length == 1){
return nums;
}
for(let i = 0 ; i < nums.length ; i++){
h[Math.abs(nums[i])]++;
}
for(let i = 0 ; i < h.length ; i++){
if(h[i] == 1){
return i;
}
}
Can anyone tell is my approach correct or not.
And it does work for positive number but not negative 😅
Thanks!