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.
Simply brilliant! This is the best channel for LeetCode walkthroughs on UA-cam. The way you explain how to develop intuition for this problem is truly next level.
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.
@@ah_sheta I've noticed bit manipulation is like the last resort for a constant space solution. There are a lot of popular problems that can also be solved with bit manip in constant space. But I agree - I couldn't figure out the xor solution lol!
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.
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!
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
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
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?
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.
@@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
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.
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.
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 😅
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.
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
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 UA-cam.
The way you explain how to develop intuition for this problem is truly next level.
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.
@@leonscander1431 I also thought about adding and subtracting, but why did you thought of XOR after that (I mean.. is there any particular reason)?
@@ah_sheta I've noticed bit manipulation is like the last resort for a constant space solution. There are a lot of popular problems that can also be solved with bit manip in constant space. But I agree - I couldn't figure out the xor solution lol!
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
Thanks!
Thank you so much!!
A difficult concept, thanks a lot!
Your explanation is so good
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!
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...?
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!
Never thought like this it can be solved. Good bro🙂
Brilliant explanation
Awesome explanation!
What a cool solution. Love it.👍
I come up with this solution by myself！ I am clever😁
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
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.
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 😰
ultra fast and memory lean one-liner: reduce(xor, nums) , reduce from functools, xor from operator
Thank you very much
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.
i solved it like this:
for index in range(len(nums)):
if nums.count(nums[index])==1:
return nums[index]
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
i would never ever think about it
return reduce(lambda a, b: a ^ b, nums)
return reduce(operator.xor, nums)
result=0
for i in nums:
result ^= i
return result
thank you
Love you man!
Thank you so much!
In the starting you mention for hashset 2 be removed completely. Shouldnt it just be one time
Would you consider doing fair indexes Leetcode 1882?
What's up bro, ur videos are really helpful thanks 💯
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
U a Single Number God
Thanks
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?
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.
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
Thanx
what if the repeated numbers were repeated n extra times instead of 2 , eg 3
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"
bit manipulation coding questions should be banned from coding interviews
for ele in set(nums) :
if nums.count(ele) == 1 :
return ele
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
take an XOR of the elements.
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
0 xor 1 gives 1
done
This is giving me wrong answer. Anybody know why?
First view first like 🤞
can someone explain me from 4:11
🔥🔥🔥🔥
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
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 😅
xor ^
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!
😀😀😀
lol love this problem,
please never stop
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
Thanks!