Interview Question: Two Missing Numbers

[@TheSrini007]

Amazing Solution. Without Memoization, I could not think of considering the half-of-sum idea. Brilliant!

[@ByteByByte]

thanks!

[@josephluce3801]

First off, thanks for making these videos, there aren't enough coding interview videos out there on KZbin. I'm considering making some of my own one day. Good job! Secondly, as a software engineer to another software engineer, I have a interview question I'd like you to solve in one of your videos. I think it would be a great one for the viewers. You are building a binary search tree from scratch. In your design, you are to implement a method to find a random node in that tree where each node has equal chance of being selected.

[@ByteByByte]

Thanks! :) That sounds like an interesting question. Do you know of a better solution than either generating the tree, then assigning numbers to each node and randomly picking one, or doing an online algorithm where you randomly select or reject each node as you go?

[@josephluce3801]

I'll send you an email of the explanation, you'd have to be very careful with your concept to maintain that 'equal chance' probability for all nodes.

[@basheeral-momani2032]

I liked your smile when you go from one solution to a better solution

[@chintalapativenkataramarahul]

I think it is enough if we compute one xor i.e either left one or right one. Then we can simply subtract it from (totalSum-arrSum). I think it is a little more efficient that way(But not significantly).

[@usman9571]

Dude, just wanted to say you're an awesome teacher! Thanks for taking out the time to make these videos!

[@ByteByByte]

Thanks!

[@neelimagupta4921]

How to solve problem if given array is {3, 4, 5, 6} and missing numbers are 1, 2 ? in this case, both missing nos are on left side of pivot.

[@ByteByByte]

totalSum - arrSum / 2 = 3/2 = 1. You still pivot in the same way and end up with 1 on one side and 2^3^4^5^6 on the other.

[@mohdrasid6737]

I was also thinking of this case... we are XORing of those numbers which are( less or equal to the pivot) or (greater than the pivot) ...so no matter where these numbers appear in array , only one element come from Left XOR and one from right XOR. ☺

[@rajrsa]

@ByteByByte Won't the oneMissing solution break down? Because 1^2 = 3 (calculating totalXOR) and then when you try to go 3, it is 3^3 which is 0, so you get an incorrect sum? Also, I absolutely loved this playlist. It would be great if you could add more videos!!

[@falakk22]

Great illustration of problem towards complex form ,Thanks.

[@ByteByByte]

you're welcome!

[@Dyslexic_Neuron]

more of a maths question than programming!! Good Explanation bro :D

[@roberthelk6492]

I think one solution to this would be similar to your Find All Duplicated one. Only caveat being that either data is signed type or n < MAX/2 which would allow to add n to current value. Array size is not issue since due to required size is Source + Answer in length so can use answer part to make up. Just initialize them equal to first element of source array to avoid complications.

[@ByteByByte]

Interesting, hadn't though of doing it that way, but you're right that would work too. Thanks for sharing!

[@yuvrajoberoi7834]

The solution is brilliant man

[@priyankarrajgupta4198]

Will this solution ends up in a overflow when n is sufficiently large.

[@amellperalta]

Great job! Please, can you make a tutorial explaining problem 16.3 of Cracking the Coding Interview. You already made a tutorial explaining a similar problem, but I think it would be good to explain that one, too. The problem says: Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any. Thank you.

[@ByteByByte]

Hey thanks for the suggestion! I actually already did a solution to that problem, which you can see here :) www.byte-by-byte.com/lineintersection/

[@dheerajnadakatla7118]

This solution in mind blowing!

[@HallaBool]

Excellent video, but a few points about the solution: 1. Here you incorrectly assume the array is already sorted. The problem statement doesn't specify that. 2. You don't have to calculate the second missing element, just subtract the (TotalSum - arrSum)-(firstMissingElement).

[@ByteByByte]

1. What makes you think the array needs to be sorted? This solution shouldn't require that. 2. In this case how are you calculating firstMissingSum to begin with?

[@HallaBool]

Thanks for your response. To address your points: 1. The step when you get the pivot index, on the array, once you get the total sum. You look for the missing array element in index lower than the pivot index. This can only be true if the array is sorted. 2. You get the first missing number by following the step you mention (to get the first missing element in the lower half). But instead of doing the lookup for the upper half for the second missing element. Just take the difference between the first missing element and the totalSum of the missing elements. For Example: Lets say the totalSum missing is 8 and the first missing element is 3, then we can just do a 8 - 3 to get the second missing element.

[@ByteByByte]

1. So when you're pivoting, you're not actually paying any attention to the order, you're just saying for each element is it greater or less than the pivot. Therefore it's not actually reliant on the order. 2. Yes you could do that, but that doesn't really seem like any less effort to me

[@aravindhravichandran5152]

Someshwar Chatterjee your question is intuitive ... but if we closely look in the pivot calculation. let's say the given array is [4 1 5] size = size+2 so size =5 totalsum = (5*6)/2=15 arrsum=4+1+5=10 pivot =(15-10)/2=2 it means that the value one value will lie between (1,2) and other between (3,5). a clear understanding can be with this example given array is [3 1 2] now totalsum= 15 arrsum=6 pivot = 4 so one value will definitely lite between (1,4) and the other will lie between (5,5) (which is five itself ).. did I make sense?

[@atishnarlawar1177]

Just want to get clarified, as I had the same question. The algorithm calculates xor on the based of comparing pivot value with array elements and not with array's pivot index.

[@dailyclassicwowmoments6395]

Such a great idea to use XOR here wouldn't have thought about that one, thanks for the video.

[@evayang1398]

It's really inspiring! Thanks for the video!

[@itaycarpis9291]

XOR is not needed here at all. Take a look: void TwoMissing(int* arr, int size, int* first, int* second) { int total = 0; int arrTotal = 0; for (int i = 1; i

[@swapniljain3459]

i thought calculation for a sum of sequence of numbers is [(n)(n+1)/2 ] rather than [(n)(n-1)/2]]

[@ByteByByte]

yep you're right; its corrected in the blog post

[@kimerseen8934]

n*(n-1)/2 if sequence starts with 0

[@swapniljain3459]

Kimer Seen yes but sequence of n numbers is always considered as starting from 1 rather than 0.

[@hamiddoust8004]

Awesome explanation !!

[@ByteByByte]

thanks!

[@pranavkumar9943]

Hello Sam. Recently subscribed to your channel. It's really great work man. Thanks a lot. Can you suggest where I can find programming questions like these, please ??

[@nikhilgoyal8340]

Using the quadratic equation class Test { public static void main(String[] args) { int n = 5; int[] a = {1, 3, 5}; int sumOfElements = (n * (n + 1) / 2) - getSumOrProduct(a, true); int productOfElements = getFactorial(n) / getSumOrProduct(a, false); double discriminant = (Math.pow(sumOfElements, 2) - 4 * productOfElements); int x = (sumOfElements + (int) Math.sqrt(discriminant)) / 2; int y = (sumOfElements - (int) Math.sqrt(discriminant)) / 2; System.out.println(x); System.out.println(y); } private static int getSumOrProduct(int[] a, boolean getSum) { int sum = 0; int product = 1; for (int element : a) { sum += element; product *= element; } if (getSum) { return sum; } return product; } private static int getFactorial(int n) { int factorial = 1; for (int i = 1; i

[@Famctabe]

It seems like you could use this technique for k missing numbers by calculating xor overlaps on k sections but at some point you would exceed O(n) time.

[@ByteByByte]

You can definitely generalize the algorithm, although it gets a bit more complicated. There is some discussion of that here if you're curious stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe

[@khemchandrs]

Is given array is sorted?

[@robinthakur7050]

hey can b done in o(n) . we know a+b we can find a2+b2 using summation of first n sq numbers then solve the 2 eq

[@ByteByByte]

this solution is already O(n). And sum of squares is a bit dangerous considering overflow

[@robinthakur7050]

Byte By Byte Thanks for the reply I just thought that it was simpler .In fact using this it should tkae constant time ...keep up the gud work buddy..

[@Nmx7428]

what if we take input form user what is expected code change we have to made

[@anuragpundir1483]

Dude you are awesome , Keep up the good work (thumbsup)

[@ByteByByte]

thanks!

[@stephenchen2011]

It's a nice video, curious, what happen if array starts with 0, such as {0}, or {0, 1, 3}?

[@ByteByByte]

pretty much by definition, we need to start with 1, because otherwise you can't differentiate between an array missing 0 or missing a number at the end

[@alejandroguzman4619]

Does it work for arrays that are not sorted?

[@deepaakanoi8544]

Yes

[@gepliprl8558]

Thank you man. 👌☝👍

[@loneshaan8531]

totalSum formulla is wrong , it should be => totalSum = size * (size + 1) / 2. en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF UPDATE: he has corrected himself at the end of this video

[@mohdrasid6737]

must watch 🥰

[@basheeral-momani2032]

You are awesome

[@avinashpathak7563]

what about when we want find k missing number in range 1 to n

[@ByteByByte]

THat's a different problem

[@milpitas1985]

Running time is incorrect unless it is given that input array is sorted.

[@sparrownature9189]

How about if first 2 numbers missing, for example [3,4,5]

[@deepaakanoi8544]

It will.still wirk fine

[@coolgoose8555]

This implementation will fail on this example: Range [0-5] i.e. A' = [0, 1, 2, 3, 4, 5] and input arr A = [5, 3, 0, 4]. As per implementation in this video pivot = (15 - 12)/2 = 1. TotalLeftXOR = 1 (As i starts from 1) arrLeftXOR = 5 TotalRightXOR = 2 ^ 3 ^ 4 ^ 5 = 0 arrRightXOR = 3 ^ 0 ^ 4 = 7 {1^5, 0^7} = {4, 7} Am I missing something?

[@alexandruteodor3585]

Wouldn't it be much simpler to solve this problem with an occurence array?

[@aamirjamal6833]

How do we know that the missing numbers in [1, 2, 4] are 3 and 5? Couldn't it be 0 and 3? Will the pattern always start with 1?

[@mrizigarouiass6474]

!!! your solution does Not work when the two elements are at the beginning or at the end. sum = numberOfelements *( average) sum = numberOfelements* ((min+max)/2) [.... min, ..... max] when two elements are missing at the end, we have new max = max+2; sum = (numberOfelements+2) *( (min+max+2)/2) the average is min+max+2 (missing elements at the end) sum = (numberOfelements+2) *((min-2 + max)/2) the average is min-2+max (missing elts at the beginning) Thanks

[@alexandersmirnov4274]

size * (size + 1) / 2 not (size - 1)

[@b11918]

there is a more easy solution than this using set_difference method in c++ would find out the ans and that could also find n number of missing characters in the array !!!

[@ByteByByte]

yes you could use built in functions to do the work for you but that kind of defeats the purpose

[@b11918]

defeats the purpose ! why ? i am a fresher and if in interview if this same question is asked and i answer it through set_difference will it be wrong ?

[@ByteByByte]

its like me asking you to sort an array and you using Arrays.sort. Yes it gives the same result but the only thing I learn about you is that you know that Arrays.sort exists.

[@scottstoll-dn2yx]

Just FYI: I know it's written XOR but I've never heard it pronounced "X OR". Everywhere I've been, we always said "exclusive or". (But we used the abbreviation in writing!)