This is not a logical explanation. You're simply telling a trick and how you found a solution. The idea behind this method is: Lets say every integer has a pair except for the lonely integer. Imagine xor'ing the similar ones . So num-xor-num is 0. Eventually you are doing 0-xor-lonelyinteger and any number xor 0 is the number itself.
Anupama Kumar not exactly it is a very simple logic x XOR x = 0; so xor every number in the list [except the lonely one) gives us 0 . Rest of logic I’ll leave it you!
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.
Another very useful video. However, some of the dialogue is hard to understand because of the speed of delivery. English is my first language and I can only imagine how tough some sections of this would be to understand for a non-native English speaker. Not much good if your interviewer can not understand what you're saying.
I suggest everyone to use Map rather then learning unnecessary programs and wasting time.Just put array in hash-map and count the single entry ,thats it..
Exactly. One if the biggest issues I see if applicants is that sometimes we over engineer things. Remember, in this field the simplest solution is often the best solution because as developers we gave to account for maintainability. Your solution is more readily understood by a beginner.
In embedded you typically do not have hashtables, or even memory to keep a second copy of the array, often data is not even stored in memory but in some sort of storage that you must read and write in blocks. Execution speed of the proposed solution is much faster even if the asymptotic complexity is the same. Not all jobs are backend software in a language that has an extensive library of ready made data structures
if it was just two #s then it looks at each bit and if they are different put a 1 in that space, if they are the same put a 0. That will give you the XOR of two #s. 0010 1010 _________ 1000
This is not a logical explanation. You're simply telling a trick and how you found a solution.
The idea behind this method is:
Lets say every integer has a pair except for the lonely integer. Imagine xor'ing the similar ones . So num-xor-num is 0. Eventually you are doing 0-xor-lonelyinteger and any number xor 0 is the number itself.
Anupama Kumar not exactly it is a very simple logic x XOR x = 0; so xor every number in the list [except the lonely one) gives us 0 . Rest of logic I’ll leave it you!
Thank you
This blew my mind... So damn clever
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.
You rock bro.
I love this solution. I you test it with a 2 millions elements list it will take only 186 ms to process and get the right result. Amazing.
Hello, the URL link in the video description is broken.
Another very useful video. However, some of the dialogue is hard to understand because of the speed of delivery. English is my first language and I can only imagine how tough some sections of this would be to understand for a non-native English speaker. Not much good if your interviewer can not understand what you're saying.
I suggest everyone to use Map rather then learning unnecessary programs and wasting time.Just put array in hash-map and count the single entry ,thats it..
Exactly. One if the biggest issues I see if applicants is that sometimes we over engineer things. Remember, in this field the simplest solution is often the best solution because as developers we gave to account for maintainability. Your solution is more readily understood by a beginner.
In embedded you typically do not have hashtables, or even memory to keep a second copy of the array, often data is not even stored in memory but in some sort of storage that you must read and write in blocks. Execution speed of the proposed solution is much faster even if the asymptotic complexity is the same. Not all jobs are backend software in a language that has an extensive library of ready made data structures
Great little trick.
I might add it works every time the number of duplicates is even.
This solution will work for a single lonely integer only in a given collection of integers.
That is the problem statement. The function has to return an int - not a collection of lonely integers.
Lost me at "if we XOR all of these" unprofessional. Operation should go from left to right.
nice
Doesn't explain what XOR is :-(
if it was just two #s then it looks at each bit and if they are different put a 1 in that space, if they are the same put a 0. That will give you the XOR of two #s.
0010
1010
_________
1000
XOR = exclusive OR. Meaning that one (and ONLY one) bit is set.
ex: 1 XOR 1 = false, 1 XOR 0 = true, 0 XOR 1 = true
There is a video on bit manipulation earlier on in this series which explains it. Watch the videos in order
speed so fast so that i could not understand the means of all with listening non-mother tongue.