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.

@cringemasteralmyrph3757

2 жыл бұрын

When i tell you i laughed when you mentioned he said "but that's just math". Like, "Ya, duh. Is this your first time figuring out that programming and algorithms ARE 'just math' ??" lmaooooo

@NodeBear

2 жыл бұрын

should pass you to the next round the moment you mentioned the formula lol...

@davidaw104

2 жыл бұрын

I know it's maths but his explanation makes sense.

@ViktorKishankov

2 жыл бұрын

Yep, interviewer just may say: formula is great and valid, now can you solve it without formula?

@rukna3775

2 жыл бұрын

@@cringemasteralmyrph3757 except its not lol

(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

@samsegalloldude

2 жыл бұрын

Any chance you'll translate that to c++ or c? from what I can tell in the video it's not clear how xor is applied between the shown 2 arrays. EDIT: Figured it out, as I previously thought about XORing each element in the array with the next element. My C code solution for this: int missingNumber(int* nums, int numsSize) { int i = 0; int whole_n_sequence = 0; for (i = 1; i { nums[i] ^= nums[i - 1]; //Xor each element in nums with the next one whole_n_sequence ^= i; //Xor whole numbers in sequence 0,1,2, ... n. } whole_n_sequence ^= i; //Xor last i (loop starts from i = 1) return whole_n_sequence ^ nums[numsSize-1]; }

@andytorres1556

Жыл бұрын

@@samsegalloldude in c++ : int missingNumber(vector& nums) { int res = nums.size(); for(int i = 0; i res ^= i^nums[i]; } return res; }

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

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

@frankl1

2 жыл бұрын

I used gauss also, but I agree that the way he solved the problem is much more cleaner

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

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

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

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)

@xl0xl0xl0

2 жыл бұрын

This is the best solution.

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)

Thank you for clearing this problem!

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

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

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

@mirrorinfinite5392

Жыл бұрын

how will you know which are the missing numbers from the answer?

@servantofthelord8147

13 күн бұрын

@@mirrorinfinite5392 i'm also curious about this

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

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

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)"

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

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)?

Very clear explanation.. Thanks Man.

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 🙂

@vibhasnaik1234

2 жыл бұрын

because boolean logic is both associative and commutative. 5^(3^5) 5^(5^3) - commutative property (5^5)^3 - associative property = 3

Everytime, when you say how long or how much memory it's gonna use. How do you know?

at the start the example about the hash map, wouldn't it be o(n*2) run time instead of O(n) as you will have will need a loop to create the hash map first ?

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

Where in the code is XOR happening? I am confused. Is it res += (i - nums[i])? If so, why does that work? Is it Python exclusive syntax, and I need to figure out what Python is doing under the hood in order to translate it to Java? From what I can see, this should just subtract nums[i] from i and add it to res. I tried implementing this in Java, and ran into the error `local variables referenced from a lambda expression must be final or effectively final`. The solution I found for this is to create a second variable to be final. I'm thinking this makes it impossible to implement this solution in O(1) extra space. But I'll keep trying. Edit: Nevermind. I put the question into ChatGPT, and got a working answer. I'm looking into how it works now. The Answer: int missing = nums.length; for (int i = 0; i missing ^= i ^ nums[i]; } return missing; I feel that this video was a bit rushed, and the breakdown of how the code is following the logic of your higher level explanation is sort of lacking. Still, thanks for the video.

Wow, the XOR solution was so cool.

This is so confusing to me. I've watched it several times. The solution looks simple, but something is throwing me off. What does "res = len(nums)" do?? I don't get why you changed it from 0.

@nickleo4308

4 ай бұрын

@77794471 6 months ago (edited) Range function in python just increments and stops at the number. Say you put in 3, the loop will iterate 3 times before stopping. Issue is you'll be left with 0,1,2. So in order to get that last number we just pre initialized res = len(nums), this way we also get the last number for our results.(copied and pasted the above comment) i had the same doubt too lol

Brilliant explanation... can you please explain this problem also:1060. Missing Element in Sorted Array. I am break my head on Binary search solution for this problem. No matter how many other videos i see im still not getting it. I appreciate your help. Thanks in advance.

Excellent explanation

same solution but I think a little less confusing, sum needs to be sum of [1,n] so just add 1 def missingNumber(self, nums: List[int]) -> int: res = 0 for i in range(len(nums)): res += ((i + 1) - nums[i]) return res

Thank You for your work😍😍😍

Can't we just sum the elements in the array and perform subtraction with the expected sum without the number to get the missing element

@triscuit5103

2 жыл бұрын

Sup babe? Well, in theory, you could. However, you are going to have overflow issues if the numbers are too big. You get what I mean babe? Like, say X is the maximum positive integer your system supports, and say the array has X-1 and X-2, and you add them up, boooooom, it explodes.

@bobbyd1658

2 жыл бұрын

@@triscuit5103 For leetcode Tom's solution works, because the problem states that n will never be bigger than 10000.

@nvm3172

2 жыл бұрын

@@bobbyd1658 yes

@fahid3342

2 жыл бұрын

@@triscuit5103 Why did you say "babe"? You're so damn awkward and cringe. Lmfao

Thank you a lot sir

I hate how sometime I just overthink 😤

O(nlogn), const space 5ms Java... sometimes when i cannot come up with O(n) but a solution i design gets accepted, it feels everything is worth it.. class Solution { public int missingNumber(int[] nums) { /*range : 0 to array length */ Arrays.sort(nums); if(nums[0]!=0){ return 0; } for(int i=0;i

def missingNumber(self, nums: List[int]) -> int: maxi = 1e5 for i in range(len(nums)): idx = int(nums[i]%maxi) if idx

Question is even easier now! Doesn't have to be O(n) time complexity last time I checked. lol

@LWeRNeO

2 жыл бұрын

still has to be O(n)

Generate a new array from 0 to the length of the array plus one. Add all elements of this new array. Then, add the elements of the given array. Finally, subtract the sum of the first array from the sum of the second array. example code: def missing_num(mylist: list): array_length = len(mylist) + 1 array = list(range(array_length)) return sum(array) - sum(mylist)

interesting approaches

the javascript one line equivalent: ``` [0,1,3].reduce((prev, elem, idx) => (prev + (idx + 1) - elem) , 0) ```

I got asked this in an interview and used the arithmetic series(math). The interviewer followed up by asking what I would do if two numbers are missing. Why do we keep missing numbers lol? but anyways it went from Coding interview to basically solving a quadratic equation using the sum of squares formula in addition to the arithmetic series. :(

I found out a easy solution but because of sorting it make time complexity o(logn) , Space complextiy remains constant sort(nums.begin(), nums.end()); int count = 0; for(int i=0; i

2 lines O(n) solution var missingNumber = function(nums) { let sum = nums.reduce((sum,num)=>sum+num); return ((nums.length*(nums.length+1))/2)-sum; };

class Solution: def missingNumber(self, nums: List[int]) -> int: nums = set(nums) for i in range(len(nums)+1): if i not in nums: return i

@simonzouki4570

2 жыл бұрын

this needs O(n) space

@slayerzerg

2 жыл бұрын

@@simonzouki4570 it is O(n) time and space

@elgizabbasov1963

2 жыл бұрын

​@@slayerzerg hb this res = len(nums) + 1 for i in range(0, res): if i not in nums: return i

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

Thanks!

@NeetCode

2 жыл бұрын

Hi Huy - thank you so much, I really appreciate it!! 😊

@cloud-vietnam

2 жыл бұрын

@@NeetCode thank you so much

Um so I wrote this code and it cleared all the test cases, can someone tell me why this would not work? class Solution(object): def missingNumber(self, nums): for i in range(len(nums)+1): if i not in nums: return i If there are more numbers could we just not use a list to store it?

@alejandrodardon7091

2 жыл бұрын

It does work but it would be worst case O(n^2) because each time you check if its not in nums you are essentially going through the entire array again.

This works better: x = (set(range(len(nums)+1)).symmetric_difference(nums)) return list(x)[0]

return sum([i for i in range(len(nums)+1)])-sum(nums) 🤷‍♂

to be honest I did not understand why we initialize our res = len(nums) at the beginning?

@77794471

10 ай бұрын

Range function in python just increments and stops at the number. Say you put in 3, the loop will iterate 3 times before stopping. Issue is you'll be left with 0,1,2. So in order to get that last number we just pre initialized res = len(nums), this way we also get the last number for our results.

@yasmineelhadi5511

10 ай бұрын

@@77794471 I was so confused but tysm for the explanation!

class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ num = (sum(range(0, len(nums) + 1)) - sum(nums)) return num

Here is a O(1) Time and Space complexity solution return ((len(nums) * (len(nums) + 1)) // 2) - sum(nums) # O(1) Explaination: I am calculating the the total size of n natural integers using the formulae (n * (n+1)/2) rather than iterating over nums.

def missingNumber(self, nums: List[int]) -> int: n = len(nums) sum = (n * (n+1))//2 for num in nums: sum = sum - num return 0 if sum == 0 else sum using n*(n+1)/2

You can also just get the sum of the array and subtract the sum of the full array using the triangular's numbers formula

@triscuit5103

2 жыл бұрын

Sup babe? Well, in theory, you could. However, you are going to have overflow issues if the numbers are too big. You get what I mean babe? Like, say X is the maximum positive integer your system supports, and say the array has X-1 and X-2, and you add them up, boooooom, it explodes.

Can I do this: def missingNumber(self, nums: List[int]) -> int: return sum(range(len(nums)+1)) - sum(nums)

I still have no idea what is going on but thank you!

@shanemarchan658

Жыл бұрын

function missing_num(arr) { let x1 , x2 for (let i = 1; i

I figure out this solution which T.C = O(n) and M.C = O(1) class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) s = n*(n+1)/2 for i in nums: s -= i return int(s) #

Here is a solution using XOR for those of you who wants a more explicit XOR approach def missingNumber(nums): n = len(nums) xor_all_indices = 0 xor_all_elements = 0 for i in range(n + 1): xor_all_indices ^= i for num in nums: xor_all_elements ^= num return xor_all_indices ^ xor_all_elements

Is this solution not optimal? sorting the list and then comparing it with its index rearranged = nums.sort() for i in range(len(nums)): if i != nums[i]: return i return i + 1

@alejandrodardon7091

2 жыл бұрын

Depends what your given programming language's sort function does under the hood, python for example uses quick sort I think which is O(nlogn) as opposed to the methods he used which are O(n)

@anasofiamartinezaguilar2494

2 жыл бұрын

@@alejandrodardon7091 i had the same question, thank you! Great explanation

this probably is the smartest way to code this :) n = len(nums) res = 0.5*n*(n+1) - sum(nums) return int(res)

@triscuit5103

2 жыл бұрын

Sup babe? Well, in theory, you could. However, you are going to have overflow issues if the numbers are too big. You get what I mean babe? Like, say X is the maximum positive integer your system supports, and say the array has X-1 and X-2, and you add them up, boooooom, it explodes.

@shoham21

2 жыл бұрын

shorter is return (int)((len(nums)*(len(nums)+1))/2)-sum(nums) :)

def missingNumber(self, nums: List[int]) -> int: n = len(nums) s = (n * (n + 1)) // 2 val = sum(nums) return s - val

Can't we just do it by simply iterating 'i' from 0 to n+1 and check if 'i' is present in given array

@ayushraj6525

3 жыл бұрын

Nah because before doing that you have to sort the array which will atleast take O(nlogn) time..But according to the question you have to solve it in o(n) time complexity

@mohithadiyal6083

3 жыл бұрын

@@ayushraj6525 thanks 👍🏻

@farjanashaik9601

2 жыл бұрын

@@ayushraj6525 hey! i did it without sorting them time was 3321ms where as for just adding it was 189ms i dont know why is it because of if block may be and the code was: for i in range(len(nums)+1): if i not in nums: return i

@MichaelShingo

Жыл бұрын

It's very inefficient because the "in" operator is an O(n) operation. You're doing this every time the loop runs, so your time complexity is O(n^2). If you convert the array to a set() with O(1) lookup time, it helps the time complexity, but now you've used O(n) space.

return len(nums)*(len(nums)+1)//2 - sum(nums)

Can we simply do this `return sum(range(len(nums) + 1)) - sum(nums)`

@studiouspanda1999

2 жыл бұрын

yes, only if the question allows for O(n) extra space, the leet code expects you to solve it in O(1) extra space.

pls teach code in java , it would help a lot thanks :) , love your explanation.

kzread.info/dash/bejne/iaKErrWLfLanfqg.html actually you can sum two arrays in one loop, so it can be O(n) as well

By looking at the ranges, 0

@alejandrodardon7091

2 жыл бұрын

Not too sure on this but wouldn't than be O(n^2)? Because you are essentially checking the whole array each time to see if the given index is in the array?

@zactamzhermin1434

Жыл бұрын

@@alejandrodardon7091 yep, O(n^2) time O(1) space if nums is a list; O(n) time O(n) space if nums is first converted to a hashset; both are sub-optimal solutions

i mean the dude sounds exactly like the daily dose of internet guy

I have solved this with the equation. BUT I am trying the codes at the end but that's giving me INCORRECT ANSWER. What am I missing here? NVM, Got it right finally while trying out with pen and paper! Thanks NeetCode

i used simple mathematics c = len(nums) d = sum(nums) f = (c*(c+1))//2 - d return f

Solution with generator, in-place addition, and re-use of variable: class Solution: def missingNumber(self, nums: List[int]) -> int: res = len(nums) res += sum(i - nums[i] for i in range(res)) return res

I've used a different approach. I got the maximum value in the list and sorted my list first then, I run the loop till (max val + 1) and checked whether i != nums[nums[i]]. if that's not the case then i += 1and if we get if condition correct, then we return i which is the missing value time - O(n) Space - O(1)

Wrong Answer!

one line class Solution: def missingNumber(self, nums: List[int]) -> int: return sum( [_ for _ in range(len(nums)+1) ] ) - sum(nums)

Here something that should work: class Solution: def missingNumber(self, nums: List[int]) -> int: for i in range(0, len(nums)+1): if i not in nums: return i

@Rahul-wv1qc

2 жыл бұрын

O(n) time. we need to come with a better solution. converting list to a set/dict will make O(1) time and O(n) space

@AdityaVarmaMudunuri

2 жыл бұрын

@@Rahul-wv1qc That is not O(n) time. the i in nums lookup takes O(n) since its a list. Its O(n^2)

Java public static int findMissingNumber(int[] arr) { int ans = 0; for (int i=0; i

7 ^ 0 is not the number itself

@tempomiss8530

3 жыл бұрын

7^0 is 7 itself

@chrisbrophy7508

3 жыл бұрын

@@tempomiss8530 7^1 is itself

@saatvik1585

3 жыл бұрын

@@chrisbrophy7508 its an XOR

@tempomiss8530

3 жыл бұрын

@@chrisbrophy7508 here 7^0 doesn't mean 7 power zero. 7^0 means 7 xor 0. (Atleast in c++)

class Solution { public int missingNumber(int[] nums) { int currSum = 0; int expected = 0; int n = nums.length; for(int i = 0;i

public int missingNumber(int[] nums) { int xor = nums.length; for(int i=0;i

nums.sort() for i in range(0,len(nums)): if i!=nums[i]: return i return len(nums)

class Solution: def missingNumber(self, nums: List[int]) -> int: f1 = sum(nums) n = len(nums) x = n*(n+1)/2 return int(x-f1)