Missing Number - Blind 75 - Leetcode 268 - Python

0:00 - Read the problem
2:42 - XOR Explanation
8:02 - Sum Explanation
9:20 - Coding Explanation

leetcode 268

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

[supercarpro]

Friggin calculus taught me the sum is just n(n+1)/2 so just loop through array and keep subtracting from that, remaining will be result. Tried using that formula in an interview once and bro was just like "but thats just math" and ignored it lmao. Thanks for the vids, really high quality and I get excited seeing you covered a problem I need help on.

[musicgotmelike]

Really appreciate the fact that you explain multiple solutions. Always interesting to learn them!

[robogirlTinker]

(Python - XOR)
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i in range(len(nums)):
res ^= i ^ nums[i]
return res

[juliagulia]

The way you coded it is so much cleaner, thank you! I was using my handy gauss summation formula but adding and subtracting seems way easier

[sealwithawkwardness]

I'm glad that math finally kicked in for me, remembering Gauss's formula for sums.

[triscuit]

The clearest explanation I've seen on this. Hot stuff. Thanks for your videos, they are the bomb.

[varswe]

because of you i am feeling addicted to these problems, now i am sure with some time and practice i will get in Big Tech

[lee_land_y]

you can also use a closed for of sequence (1 + 2 + ...+ n) and subtract a sum of nums. solution would be len(nums)*(len(nums) + 1) / 2 - sum(nums)

[vdyb]

Such a clean and clear solution !!! Awesome !!

[vishalsinghsengar]

I was asked the same question in interview, with a twist that more than 1 number can be missing, with that the sum() logic doesn't work. But the XOR logic will

[kaiserkonok]

Aww. One of the best explanation🔥Thank you so much🖤

[codeisawesome]

Thanks for the upload! I grokked the XOR explanation much better thanks to this as the Leetcode editorial was incomprehensible. Feedback: would've been a bit nicer if the explanation of why 5^3^5 would yield 3 - even though the order is not 5^5^3. I was able to work it out on paper, but the video would be more complete that way 🙂

[PASTRAMIKick]

I used the Triangular number formula: ((n^2) + n) / 2, for calculating the total sum of the full range and then substracted the sum of the numbers in the given array. Ends up being O(n) for time and O(1) for space

[skyplanet]

Thanks for the video. A more general form that can handle any array is this
"def missingNumber(array):
res_all=0
for i in range(min(array), max(array)):

res_all+=i-array[i]
return res_all+max(array)"

[VibeBlind]

result = len(nums)
for i, n in enumerate(nums):
result += i-n
return result

[montopy]

Doesn't regular sum arguably take O(lg n) space since you need bits scaling logarithmically with the total sum and length?

[jose.ambrosio]

Your videos are helping me a lot. Thanks, Neetcode!

I implemented a simpler solution for this problem with the same time and memory complexity.

class Solution:
def missingNumber(self, nums: List[int]) -> int:
sumAll = 0

for i in range(len(nums) + 1):
sumAll += i

return sumAll - sum(nums)

[mostinho]

Done thanks
Trivial solution:
Input array from 0 to n with 1 number only missing, need to figure out what the number is so fullInputSum - actualInputSum gives that element

XOR solution
When you xor two numbers that are the same output is 0
The order in which you xor numbers doesn’t matter. A xor B xor C same as A xor C xor B

So if you xor input with actual array, you are left with the missing number
Todo:- check how to xor in Java

[iseeflowers]

I love your your clear explanation and videos. I am confused about the part that hash map is O(n) for space/ memory and not O(1)?

[tenzin]

I hate how sometime I just overthink 😤