Single Number | LeetCode 136 | Amazon Coding Interview Tutorial

Single Number solution: LeetCode 136

AFFILIATE LINKS
If you're interested in learning algorithms, these are great resources.

💲 All coupons and discounts 💲

Single Number | LeetCode 136 | Amazon Coding Interview
#singlenumber #leetcode #algorithms #terriblewhiteboard #codinginterview

Click the time stamp to jump to different parts of the video.
00:00 Title
00:06 Problem readout
00:45 Whiteboard solution
01:39 Coding solution
04:24 Result and outro

[TerribleWhiteboard]

If there are any videos you'd like me to make or if you have any ideas on how to optimize this solution, let me know!

[TheCarloarg]

XOR to the rescue


(credit to kunalvats on leet)



- If we do XOR of two same number, the result will be 0. You can try this of the level of bits of the number and then performing XOR manually on it.
- If we do XOR of any number and 0. Then the result will be the number itself.


Both the properties together are used to solve this question.

[rakarez]

how if it's the array like this : [2, 2, 2, 1] or [1, 2, 2, 3, 1] ?

[yuhyunch]

if we are using a set here, aren't we violating the space complexity? (Thanks for all the videos that you posted! very helpful)

[willowsongbird]

why can't we just return the set since the set only contains the single number?

[murad]

why do we need new Set() here ???
var singleNumber = function(nums) {
let arr = [];

for(let elem of nums){
if(arr.indexOf(elem) !== -1){
arr.splice(arr.indexOf(elem), 1);
} else {
arr.push(elem);
}
}
return arr[0]
};

[sarscov]

I thought you couldn't use extra memory? You're using a set.

[SreejithNair]

/**
* @param {number[]} nums
* @return {number}
* Time complexity : O(n).
* Space complexity : O(1).

*/
var singleNumber = function(nums) {

//we can XOR all bits together to find the unique number.
let a = 0;

for(let num of nums)
{
//if we take XOR of zero and some bit, it will return that bit
//If we take XOR of two same bits, it will return 0
a ^= num;
}
return a;
};