Find Missing Observations - Leetcode 2028 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find missing observations I just want to quickly mention that I've actually already solved this problem before I even made a video for it and I think that was actually almost 3 years ago but anyways I'll solve it again today but in the future if I don't solve a problem it's worth just searching for it to see if I did it in the past so very long problem description I'll try to make it more simple for you so the idea is we have a dice this is kind of my bad drawing of it but it's six so it'll have a one on one side a two and then a three and all the way up to six so one through six and there were a bunch of rolles for those dices so I guess going through this example here there were six total rolles how do I know there were that many well because they give us a parameter rules that tells us four of them and they gave us the value of each one so that's three for the first and then 2 4 3 and they also tell us here n equals 2 so there were two more roles done we just don't know the value of those roles so that's how I know that in total there are six rows um rolles sorry but our objective here is to guess what these roles could have been not necessarily what they were because there could be multiple correct answers we just need to return a single one so the question is how can we do that it's not quite as complicated as it might seem at first let me break it down for you first of all you pretty much have to know what an average is by average I mean the mean average that's basically taking a bunch of values and then dividing them so one thing you must know you must recognize that if we were to sum all of these values so whatever that sum happened to be and then you divide it by this let's call this m that's uh the number of rols we're given and N the number of rolls we're trying to guess if you divide that by the total number of rows this sum is all of this remember this has to be less than or equal to 6 and greater than or equal to 1 the reason that this is so important is that they actually give us another parameter called the mean it is going to be this value it literally is that value so they actually helped us out because we would not be able to calculate this without the missing values it's impossible so they helped us out they gave us this value in this example the value was four so knowing that the average of all of these is four what are some realistic guesses that we could make here so now it's logical to want to know well what is the sum of all of these values we already know what M and M are so what's the total sum well that's pretty easy to calculate isn't it just take M plus n multiply it by the mean because they already gave us the sum so you know multiply both sides but uh yeah basically just take this multiply it by that this is how many rolls there were this is the average for each roll so multiplying them will give us the total in this example it is going to be 24 so it's going to be the mean was four multiplied by the total number of rols six so this is the total sum okay now it seems pretty logical to take this sum and subtract it from this so that we know well what's the total sum of the missing remaining values okay do that and you'll get this all of these I believe are 12 so we get 24 minus 12 and now we are left with 12 so this is the missing sum it doesn't tell us an individual role but just by looking at this we humans can tell that if it's 12 the only possible values that these could have been are going to be 6 and six okay but how do we do this algorithmically because it's not always going to be this simple so now that we've gone through all of these like six-sided die all this math all this blah blah blah we've reduced this to now Distributing this 12 among n different slots so now we've changed the problem this is very similar I think at least in my opinion it reminds me of like the pigeon hole principle the pigeon hole problem so that's what I'm going to be discussing now to show you how to solve this optimally let's suppose that the missing sum was 10 and we have three dice rolls to fill well okay let's just try to be greedy that always works out for us right let's try to just add the max amount that we can we have 10 here so the max we could add here remember each dice is 1 through six so that's going to be six now we have four remaining okay just be greedy add it all over here four now we have zero remaining okay just be greedy add the zero over here don't you see a problem with this approach How could a dice roll be zero it can't there is another possible problem suppose the missing sum was 19 let's do the same thing six here okay six here and then a six over here well that's the max we could have possibly done but we're still left with a missing sum of one we don't have any more dice rolls so there's two steps to this one is going to be the validation that we do before just with the missing sum value and the second step is going to be the actual like simulation it's going to be similar to a greedy approach but it's going to rely a little bit on like the pigeon hole principle thing I was talking about a second ago so the first thing we're going to do with this sum we can tell that this sum is valid or invalid just by taking this let's say we divide this by three it has to be less than or equal to six it has to it also has to be greater than or equal to 1 suppose we had a missing sum of two and we have three slots to fill well you can't really do it like one of them is going to be a zero no matter what so again the average has to be greater than or equal to 1 less than or equal to six okay now step two this is the more interesting part it's going to be somewhat greedy but the only problem is we kind of saw it earlier if we add like as much as we can here and then as much as we can eventually we run out you don't want to blow your load too quickly so let's make sure that we at least no matter how greedy we are let's at least make sure we have the bare minimum for the rest of the slots to make this more interesting let me add a fourth slot so let's just always make sure we have at least one for the remaining so we're going to do this starting with 10 we're going to add six here now we have four remaining and so now you might again think to be greedy just add that four no we have to make sure that whatever value we have that when we're left over with x that X is enough to fill these slots what's the minimum value that would be enough to fill these well there's two slots so that value has to be two what I'm saying is add the maximum value you can in each spot just make sure you have enough for the remaining spots so in this case it's a very simple formula if I were you I would try to write it out on pen and paper before I do but if you can't this is what it is it's going to be the minimum of six or the current missing sum I'll just call that sum for short minus while we're iterating through this like the code n is going to be this like the total number of slots we have here so here I'm going to do sum minus n and I'm going to do a plus one this plus one is just for the fact of this we just want to make sure that I guess I'll just give you an example of this formula when this is four this calculation is going to become a 4 minus these three + 1 so this calculation will tell us the biggest value we can put here coincidentally this is two and this length is also two this time but this calculation will tell us the biggest value that you can put here such that we at least have one remaining here and one remaining here just a dry run through this one last time maybe with a different example let's call this 13 let's do that calculation what's the minimum value we can put here it's either going to be 6 or it's going to be the sum 13 - 4 + one so that's a 10 so the biggest value we can put here is 10 and then we'd have one remaining in all of these other spots but we know that no dice can be a 10 so we put six instead the minimum of 10 and six the minimum of these two so we put a six here and I'll quickly uh go through the rest of this so now we have a seven so what's the biggest value we can put here I believe it's going to be a five and then we put a one here and then a one here now you don't have to do it this way there's no particular reason you have to put the biggest value this is just one valid answer but I believe the time complexity is going to be m + n one because we need to fill the remaining slots and also we need to compute the sum of the input rolls array space complexity I believe it's constant if you don't actually include these like output values so now let's code it up so I'll try to keep this code pretty readable let's get M that is going to be the length of that rolls parameter next let's get the total sum of everything um among rolles which again we can compute by taking the mean multiplying it by the total number of roles that's going to be m + n and then once we have the total sum it's pretty easy to compute the missing sum that we're looking for just by taking the total sum and subtracting from it the r sum which is just sum of that uh input array now remember the first thing we want to do is that validation step with the missing sum so we want to make sure that taking this dividing it by six it's going to be greater than or dividing it by n sorry is going to be greater than or equal to 6 in this if statement basically I'm going to return early I'm going to say that there isn't a possible solution so we return an empty array so for the equality here I actually don't need that if this is greater if it's strictly greater than six that's when we would return early um and then here we'll do the opposite if the missing sum and this time we actually don't need to divide it because if it's less than n n is the number of missing slots so we need at least one for each of those so this works and this kind of tells me that we can actually change this up we can multiply this side by n and multiply this side by n and then it's a little bit cleaner to have multiplication rather than division so I prefer this though it doesn't really matter too much um but now let's get into the result let's um initialize it here and then return it here but let's actually do the computation somewhere in the middle so I'm going to do this by saying while n the reason I'm using a while loop rather than a for Loop is because we're going to be updating the N variable it tells us the number of missing slots so we're going to be decrementing it by one each time but to get the actual dice in the current position remember we just take the minimum of six as well as the missing sum - n + 1 then we can add it to the result and don't forget to update the missing sum by subtracting The Dice from it so we need to keep this updated and we need to keep n updated alternatively for the condition you actually probably could have just said while the missing sum is not on zero it'll probably work the same in both cases but either way let me give this a run as you can see it works it's pretty efficient I promise you leak cut run times are pretty random this is about as efficient as you can get at least I think in terms of Big O time and space because as you can see we're not doing anything other than iterating over n and technically iterating over the roles by taking the sum of it if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon