Tuple with Same Product - Leetcode 1726 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Tuple with the same product and I really really like this problem because it involves a decent amount of math now don't worry when I say math I don't mean a bunch of formulas that you're going to have to memorize or anything like that it's going to involve some mathematical thinking so let me kind of walk you through that right now so the idea is we're given an array of distinct positive integers the fact that they're distinct is pretty convenient for us what we want to do is form all possible tupal of size four so there's going to be four elements we're going to call them A B C D and what this tupal needs to satisfy is that a * B is equal to C * D and so the thing that you need to remember about a tupal is that the order does matter so if I draw pretty much the same tupal but I just swap these two values it's still technically true we could also say B * a is equal to C * D and then we could flip the other two sides so I'll do a * B first and then B * a after that and then here we could have D * C and we could also have D * C down here you can see that while the products on both sides are the exact same we were able to rewrite the equation in four four different ways and we could actually get four additional ways just by taking all of these and putting them on the right side and taking all of these and putting them on the other side I think I said right side a second ago I meant left side sorry but basically what we've realized is that if we find four values that satisfies that condition then we've actually found eight tupal every time that happens we found eight new tupal and so that's why in the first example you can see that it's not a coincidence that we have eight over here and it's also not a coincidence in the second example we find one Formula 1 * 10 is equal to 2 * 5 each side is equal to 10 as you can see and we found a a second Formula 2 * 10 is equal to 4 * 5 each side here is 20 so this is going to be 8 tupal and this is also going to be eight tupal so we end up with a total of 16 tupal now I'm not quite done yet you might be thinking that okay well there's definitely a Brute Force solution to this problem that can run in N to the fourth time and yeah there probably is I don't know how easy it's going to be to code that up because to be honest I didn't do it it just seemed like it would have been really really tedious and also that it probably wasn't the intended solution so I was thinking of some other Solutions and that's what I'm going to show you I'm going to show you a more optimal solution that actually runs in n^2 time but before we can do that let's try to build up some intuition one thing that you could say about this second example in particular is that we had two different ways that we could total up to 10 so 1 * 10 and 2 * 5 so basically for the product that is 10 there were two ways that we could create that a number and same thing with 20 actually we could form 20 in two different ways so just to be clear this is like N1 * N2 and this is the count of how many ways we can form that if for example we had something like a 1 * 30 and we could only form 30 in a single way well then we can't really satisfy the condition a b c d where this time this is equal to that so to me it's kind of becoming clear that we don't necessarily need to Loop over everything even if we were looping over everything and we had four different loops and the first two Loops pick these two numbers well yeah we could Loop through the rest of the numbers and try to find all pairs that have the same exact value as this or why not just do some pre-computation and instead of looking at numbers four at a time why not just look at numbers two at a time and then just get the counts of those and then somehow maybe we can use these counts to determine the total number of tupal so maybe it's possible let's try by exploring this so if I had a mapping like this and I think it's obvious that probably we'd want to use a hash map or something like that for this and we could build this data structure in N SAR time just by iterating over every possible pair and then just like tracking the counts for each product suppose we did that and then we ended up with a hashmap that looks like this what exactly would we do with it well let's just scan through it and let's say okay 10 how many ways could I form that two different ways so that means I could probably build the equation a b c d in exactly one way because I have two pairs that's what this is telling me so I'm going to draw it like this I have P1 and P2 while there are technically four slots that we are trying to fill we know that each of these pairs technically makes up two different numbers we could say this is a and b and maybe this is a c and d well in this case I think it's obvious we could put one pair that fills one of them like pair slots and then the other pair would fill the other pair slot and so this way we wouldn't count this as one tupal we would count it as eight tupal and then we would scan through the other guy this over here and do pretty much the same thing so then we'd have eight additional tupal and lastly for this guy over here 30 only shows up once so actually we don't have the second pair we only had a single pair and that's definitely not enough to satisfy the entire equation so this guy we would skip so now it becomes obvious that we would only care about the ones that have a count greater than one so at least it has to be two but what if it was actually three I think this is one possible way where we could end up with three different pairs they all equal a 12 so 12 will have a count of three so that tells us we have three pairs let's call them P1 P2 and P3 we have four slots that trying to fill but we know that each is kind of grouped into a single slot so here's what we could do we could do this P1 and P2 or we could do and actually I can just kind of draw them here so P1 and P2 or we could do P1 and P3 or we could do P2 and P3 each of these is technically a different equation and part of the reason for that like the guarantee is that we know that all the numbers in the input are going to be distinct so we can kind of be sure of that but all three of these are going to be different each of these deserves a count of eight it can form eight different tupal so we'll get 8 + 8 + 8 okay so now to kind of summarize a few of the findings that we have made because while this is kind of building the intuition I don't think you're probably sure of what exactly the equation is going to be like what do we do with this count number let me kind of show you so I'm going to draw a little table over here suppose I have a count of zero well that that's going to lead to all zero so I'm actually going to skip that but if we had a count of one when I say count I mean this over here we have a product that shows up a single time well we know that we can form zero pairs and when I say pair here I mean like the equation that we can like satisfy if we only have one of these we can't really satisfy that equation if we have two of them we can satisfy that equation once so I'll put a two here and that means we can satisfy the equ once and if we had three we can actually satisfy the equation three times now if we have zero pairs or like that many times we satisfied the equation we will end up with zero tupal if we had one we will end up with eight if we have three we will end up with 24 so I'm going to fill in two more rows here and maybe you'll be able to figure out the pattern by yourself if not that's fine I'll try to clarify it now I'm not going to draw out everything to fill in the rest of this table I'm actually going to use my intuition I'm going to say if I had four count then how many like pairs from those counts could I create so like if I have four of these how many can I create well I know with three I was able to create three pairs so with three I can create three now that I have four I introduced a new one so with the introduction of this new guy how many more can I create well with four I could do four and one I could do four and two or I could do four and three so I can take three additional and put them here so whatever I had before plus three so I'm going to put a six over here and we know that to go from here to this that's like the very very straightforward part so here we'll just get 48 now one more time just to really drive this home I have five now with the introduction of P5 I can now do this this this and this so basically four more so whatever value I already had plus the count that I originally had now with the fifth I can create four more so I'll Take 6 + 4 and I'll put 10 here and then here I'll get 80 this is just a multiplication of eight so now knowing all of this there's actually two different ways to code this up one is by using a a second hashmap so we already have this hashmap up above and if we create a second hashmap which doesn't track the counts like the first hashmap is doing we will actually track this with the second hashmap so that's one approach and the second approach is there actually is a math formula that can take this value and map it to this one it can take this value and map it to that it can take this and map it to that I'll cover the math one after the hash map one I'll probably just cover this in the coding explanation but I want to briefly cover the first one because I think this one might be easier for some people who don't really like math I think this one is actually more reasonable and I think it's pretty intuitive so let me briefly cover that we're going to have a second hashmap down here so I'm just going to kind of group this into a hashmap and then down here I'm going to have my second hashmap if I see a pair suppose 1 * 12 I'm going to take 12 and increment the count here so uh let's initially say that this is zero but now we increment it to one we also know that to calculate the value here going uh from here to down here all we do is take the original value and then add to it this one so I know this part is probably like kind of complicated conceptually in terms of the code it's actually going to be pretty easy so let me just kind of show it to you let's say we initially had a zero over here we're going to take zero and add it to this second hashmap so for 12 we're going to say it's already mapping to zero so add zero to it it doesn't really do anything and then to this we're going to increment it by one this part is always going to be easy cuz we're always going to increment this by one so now let's say we found another pair of 12 maybe it's 3 * 4 I'm going to increment this by one but before I increment it by one I'm going to take the value that's here and add it down here so now I have a count of one down here and now I'm going to increment this by one and now I have two up here here so that looks uh pretty correct to me and suppose we add one more maybe it is 6 * 2 before we add one to this we're going to take this value so like this and add it to this one and that's how we find the next value that's going to go here so that's exactly what we're doing on the right side as well we're going to take this two and add it down here we're going to end up with three and then we increment this simply by one so now this will also be to three if we did it one more time then this would have been added here giving us a six down here and then this would have been incremented by one giving us a four and you can see that is indeed correct and the whole reason that we are building this second hashmap giving us all these is that we can easily take this and just multiply it by eight to get the next one which is the number of tupal and then ultimately we just want to get the total number of tuples that should be easy enough to accumulate so all this said let's jump into the code now so let me just reset this and uh what we ultimately want to do is have these two hash Maps I'm just going to copy and paste them so one is the product count so that's like N1 * N2 is how many like of those that we have also the actual number of pairs and when I say pair I mean like an A B and C D pair I know that maybe the wording of this could have been a lot better and I'm sorry about that but hopefully you kind of get what I mean so next we are just going to have a couple nested Loops so I in range and then we'll have the second pointer that will start after that just like this cuz here we want every distinct pair and then we want to take that pair and get the product so this times this and then we can take the product count and what we want to do is increment this by one but it's very very important that you only increment this after you update the pair count and the pair count is going to be updated with uh the key is going to be the same the product but we're going to add to this whatever value happens to be in the product count before we incremented it so that's why we do this I mean I guess you could move this line below this one you would just need to add a minus one here so uh just make sure you do that correctly now after all of that's done the problem becomes pretty trivial we can just do this declare our result initially it's zero that's what we want to return and then we go through every value in the pair count we don't really care about the key we just want the value and so we can say this for count in product or sorry pair count. values and then add to the result 8 multiplied by this number so that's pretty much all we have let's go ahead and run this and you can see here on the left it does work I promise you it's pretty efficient but we can improve the time complexity by a factor of two we can get it to like this range where it's about 300 milliseconds and mainly we do that just by getting rid of the second hash map I think the overhead of the second hash map is what leads to the lower runtime so let's get rid of this hashmap and let me show you the formula first I'm going to write out the formula for you you might think it's magic but then I'm going to explain it to you so we can get rid of this as well and then instead of going through the par count we'll go through the product count and to this result what we're going to add is this magic number count multiplied by count minus1 and then divide all of that by two it looks like magic and actually uh let me get rid of this this is actually equal to the number of pairs so once we have this we will add to the result 8 multiplied by the number of pairs so let me first run this you can see here it does work it does improve the time complexity I don't I think if I ran it again we might get somewhere closer to here it's not really a big deal to me but why exactly does this formula work first let me show you that table again if I have a count of one then I get zero if I have two then I get one and from five I get 10 remember the intuition of how these are calculated though this number will just be what we already had plus two more and this number will be what we already had plus three more this number will be six plus the four more so in other words if I want the number of pairs here can't I just just aggregate all of the counts can't I just say that technically 10 is equal to 1 + 2 + 3 + 4 can't I say that 6 is equal to 1 + 2 + three well yes I can I can put that into an equation but then how am I taking this and calculating it like that why don't I need a loop to do this because it's true we could get the pairs uh with a loop like we could say for I in range the count and then keep adding I to the pairs but that would obviously be less efficient so why am I using an equation to do it well it's actually pretty simple the intuition is this for this formula here I have one pair of five I have 1 + 4 which gives me 5 I also have 2 + 3 which gives me 5 so then I have that 2 + 3 if I had a longer series of numbers it would have been slightly different it would have been something like this five and six in which case I would have had 1 + 6 which gives me 7 2 + 5 gives me 7 3 + 4 also gives me seven this is a really a famous math equation I think it's pretty easy to derive like you could have kind of DED it from like the intuition I was giving you here or at least possibly but anyways I think uh the person who came up with this or at least it's attributed to a gaus when he was like a little kid but I'm pretty sure a lot of people have came up with this before um but anyways so how does all of that translate to this formula down here well if I have five that gives me 10 which is this formula um getting rid of these two and so the pair of numbers adds up to five How many pairs do we have well that's going to be count minus1 divided by two so if I wanted to I could rewrite this formula to make it a little bit more simple count multiplied by count minus1 / 2 it's technically the same if you simplify it that's just kind of how like multiplication and fractions work but maybe rewriting it this way makes it more clear and it also does work when we have an odd number of pairs so for example with six which was over here four that tells me 1 + 3 will add up to the number four How many pairs do we have well we have three numbers here so that's why I'm taking the count 4 count minus1 and then that's three I divide that by two I have 1.5 pairs so what equation will do is it'll be 4 * 1.5 that does indeed equal 6 and the reason for that is we have one pair 3 + 1 that's four and then we have half of a pair which is exactly two half of the value this is why I covered this solution after the first one I think the first one is a bit more intuitive if you're not a math person but if you like math I think this one is pretty easy as well but anyways if you found this helpful definitely check out NE code. for a lot more thanks for watching and I'll see you soon