Find missing number in an array(using summation and XOR operation)

Find the missing number in the array which contains a series of consecutive numbers in range from 1 to n. Use summation formula for natural numbers 1 to n. We can also use the XOR operation.

[@LarryRuane]

This is great, thanks! Another advantage of XOR is that there no possibility of overflow, as there is with summation. (One very minor mistake is at 4:55 you wrote "0 XOR a = 0".)

[@abhijayrajvansh]

This is great video, exactly what i needed. Indian teachers are ❤️

[@naboulsikhalid7763]

always great and concise. thank you. I would like to see the algorithm implemented in c code.

[@lojian]

Very clear.
I have a question, for your example case, could we just search from 1, to 2, to 3, until 5, when we look at 3,we know next one should be 4, and but it is actually 5; --- this assumes that array is sorted.
will XOR algo work even when array is not sorted?

[@vivekanandkhyade]

yes XOR will work on unsorted array too..

[@sivaganesh4489]

Even 1st approach also work for unsorted array but it must be sequence for both methods

[@sanapalavenkatesh5273]

you are put the add right time by the way thanks for nice explanation .............

[@PradeepSingh-vm1gl]

Love you brother. You explained so nicely. Thank you so much.

[@nasirfshah]

4:37 best way to understand XOR of n variables is that for odd number of ones(a in your case) the result is one(or a ) else it is 0.
If numbers are not sorted and duplicate entries are also there. How we can find the missing number in linear time and constant space ?

[@sakshimittal1166]

That makes a lot of sense. Thank you sir!

[@kirtivardhan80]

Asymptotically both gives O(n)
But logically 2nd one will have to iterate 2 times.
So first one must be efficient, logically.

[@darshank3012]

If the n value is high, the summation might cross the integer's max value limit, then the first approach might not work well.

[@manishswarnakar6993]

How to find multiple missing number in array ?
like an array is= {4,3,5}
so the missing numbers is = {1,6}

[@lodashnotebook5390]

Exactly what I needed. Thanks!

[@skkar2k2]

In video at (4:56), in XOR table 0 ^ a = a, while explaining 0 ^ a = 0.
But I liked the explanation. It's too nicely explained.

[@AnkitRaj-jn8ew]

Both logic has O(n) time complexity. Why not just traverse and check if a[i] != a[i-1] + 1 from (i = 1 to n-1). When the condition is true, a[i-1] is the answer. This approach is far easier and has O(n) time complexity as well. We can also use binary search and get O(log n ) time complexity.

[@jaybhatt6775]

binary search has higher space complexity

[@AnkitRaj-jn8ew]

@@jaybhatt6775 Not necessarily. You can use an iterative approach for binary search to avoid stack trace. It won't need any extra space and will be more efficient than the 2 approaches discussed here.

[@Blingblingblingling]

nice video! problem statement can be made a bit clearer: "find missing number in unsorted array", since for sorted array as in example input, it's too easy, if a[i+1] != a[i]+1 then return a[i]+1

[@ibrahimkhaleel2822]

Sir,
I have a doubt how can i ask you❓️
Pls rply

[@maheshwars.j6195]

What if multiple numbers are missing

[@durgabhavani9955]

Sir ,can you provide how to find third largest element in an array logic

[@harshivam]

just store max and second max in a variable and like how you find max just use a if statement where you check the third ma != max1,max2

[@tapanjeetroy8266]

Thanks a lot sir.. You are doing a great job

[@mangeshkumargabhane4671]

Very clear, I am looking for implementation of algorithm using any programming language. Please help if possible, Thank you very much for good algorithm videos.

[@indianmusicsongssaregama1406]

If we have scanner class then how to get sum of number.

[@Copernicus_Song]

very good explain, thx a lot!!

[@aaatatataapaatuuuu987]

Why we did xor of given numbers within same array .we can find the xor of given array and expected array. Can anyone explain me pls

[@nagesh007]

Awesome Sir

[@mustapharaimilawal8053]

Thank you so much for making this video, awesome.

[@karan6551]

Love u bro.. awesome ❤️❤️❤️

[@mohamedmusaraf675]

Superb sir!!!!

[@kumarvivek02]

Aren't you assuming here that your array is sorted? What if it is not?

[@arindam_.]

So the assumption is that the array is sorted. If not, sort the array first and then start your operation.

[@rohitdas6005]

How to find multiple missing numbers in array?

[@vickyjain3403]

sir, if you take 1 instead of ' a ' it is better for understand to us.

[@akashgowda6923]

Explanation s super but write full java code we can understand better

[@salmankhatik4985]

but how to code this in xor

[@NoorAli-uh4uq]

Thank you a-lot.

[@odalyspaz959]

Thanks for the explanation :)

[@vivekanandkhyade]

welcome Odalys..!

[@cengizandak4241]

The quickest way is the binary search which is logn

[@vikrammehta5874]

I know this method
Any other method??

[@adarshnair9846]

0 XOR a = a. U wrote it as 0 XOR a = 0 by mistake right?

[@SonuGupta-wj6dg]

nice

[@columbiars]

I don't see why the second solution is better than the first one in terms of time complexity.

[@ramakantasamal7482]

Agree on time complexity it does not help much but 1st one could cause overflow while summing

[@sachiiinnnn9734]

thanks

[@kumargourav4976]

thank you sir,

[@santhosh........]

Super sir

[@fuadhasan0362]

thank you sir...

[@techdiscussion3617]

thanks sir

[@shubhamsunny6024]

(n+1)*(n+2)/2 is actual formula, let say we have 7 is absent from range 1-9, with your formula (n*n+1)/2) 36 is coming and my array sum is 38 ,now result is 2, which is wrong.

[@getItToDeepak]

n = 9, so 9*10/2 = 45, sum of numbers = 38. Now 45-38 = 7. You got the answer

[@bryand7958]

(n * n + 1) /2 is not the formula
n * (n + 1) / 2 ==> (n^2 + n)/2

[@nileshandakshat3713]

some problems in this video

[@sahjaykumar]

Bro you learn communication. Tumhe thoda speaking course karna chahiye.. itna slow bol raha hai.

[@nileshandakshat3713]

give me reply

[@anerdwitdacamera204]

1 2 3 4…… 5 6 7 8 Ms in my bank account