Tuple with Same Product - Leetcode 1726 - Python

[@sharanvaitheeswaran]

Here is an intuitive way of looking at the problem: When we have a frequency of more than 2 for any product, the number of pairs then becomes the number of ways to choose two pairs out of the total number of pairs * 8. For example, if the product frequency count of 12 is 'x'. then the contribution of 12 to the answer is xC2*8 , i.e (x*(x-1))//2)*8.

[@motherofsuper]

Another way is to think about it as 4 * freq * (freq - 1) The 4 comes from 2! * 2! = 2 * 2 (2! is the number of ways to arrange 2 numbers, where the order matters. And we have 2 pairs here) Then freq * (freq - 1) is because we have "freq" ways to pick the first pair, and "freq - 1" ways to pick the second pair

[@Anshul-qb2pm]

combinations will be like this always 1)(ab,cd) 2)(ab,dc) 3)(ba,cd) 4(ba,dc) 5)(cd,ab) 6)(cd,ba) 7)(dc,ab) 8)(dc,ba)

[@blurryfca3]

​@@motherofsuper i made a little roundabout way and came to this in the end. Started with observing count of products of 2 numbers-> prod_freq = n. prod_freq = 1 gave 0 combinations, 2 gave 1, 3 gave 3 combinations; so came out to be n*(n-1)//2. then I noticed oh damn they are looking for permutations not combinations, so tweaked it account for permutations, 2! ways to choose a pair, 2!*2! ways to permute each pair and voila its 2!2!2!* n(n-1)//2

[@h0td0g]

man i wished neetcode explain a little more about how that formula came about. all he needed to do was to reference C(X,2) in Combinations terms and things would click so much easier. 2 hash map approach is so unnatural, if you were to get this in an interview nobody would be draw this whole thing out to find a whole ass pattern.

[@ArunKumarG-j5y]

i do have one confusion, for count 2 formula is 2 *(1//2) in python // is performs floor division right ? like for 0.5 floor value is 0 , then answer will be 2 * 0 for count 2 answer will be 0

[@VikasKumarSingh-m4h]

Heres how i solved it : valid pair makes 8 tuples so iterating over each pair and storing there product in a hashmap then check if the map has the product if it has then we can simply multiply 8 to the no of occurrences of product in the map and add to the count to get the result

[@manikishore9646]

Easiest inutition: It is a problem of combinations and permutations. Select 2 pairs from available pairs and there will be 8 permutations for each selection.

[@Avi_Bedi2125]

hope it helps: NCR = N! / (R! * (N-R)!) -> number of combinations when we have N entities and we have to select R entities out of them. Therefore, NC2 = N! / (2 * (N-2)!) = N * (N-1) / 2 this is how we get the formula!

[@yhbarve]

One of the more satisfying problems.

[@_grind_mindset]

Selecting the number of pairs from a given count is just a method of combinatorics, where we need to select 2 pairs from the given number of count. The mathematical equation is pretty simple , nCr = n!/(r!*(n-r)!). Since the case is of choosing 2 pairs the above formula can be rewritten as - (n * (n-1)) / 2, where n is the number of pairs.

[@user_unknown04]

Its just a piece of combinatorics. Basically we are choosing no. of pairs C 2. for example the no. of ways of choosing 2 things out of 4 is 4C2 = 4 * 3 / 2 = 12 / 2 = 6 and thats pretty much of it

[@vincentwong9007]

The intuition I used for understanding the maths: Pair i can be combined with the n-1 other pairs to create the tuples. Repeat for the other pairs to get a total of n*(n-1) combinations. However this doesn't account for the duplicate combinations where i,j and j,i are counted as the same combination so you use /2.

[@firasyousfi2269]

My understanding is if we check we take two pairs (a,b) and (c,d) with a product equal to X, then we have 8 possible tuples. (1) So first we create a hashmap that maps every product to how many pairs result in that product. Then we just take the point explained in (1) and we multiply by 8 the number of ways to take 2 pairs from a total of N which is C(N, 2) = N * (N - 1) / 2

[@bigmanhalalreaper2290]

what is ur paint software please

[@SandyCr7]

Sum of natrual numbers N * (N+1)/2 Just use N as N-1 (N-1) * (N-1+1) /2 (N-1) * N / 2

[@deadlyecho]

Count * (Count -1) * 4

[@emilturbo5]

One thing I couldn't understand much is: How come it requires more time and extra memory for the algorithm to return the answer of the given problem when I implement the product variable of the two integers at index i and j inside the two for-loop expressions before assigning the product as its key in the hash map, compared to directly assigning the product of the two integers at the hash map without implementing it as a separate variable? Wouldn't it make sense for the algorithm to then require less time and space for execution without needing to recompute the product value when directly assigning it to the declared hash map?

[@bertmorris9976]

For me the intuition is the number of points is an n choose 2 problem which simplifies to (n^2 -n) / 2

[@LeonLeonLeonardo]

I get the idea, but I feel like if I have to solve this problem next month, I'll need to watch this video again. :(

[@I.II..III...IIIII.....]

Gauss's sum there is really overcomplicated. You can simply do 8 * product_cnt if product_cnt is greater than 0, then product_cnt += 1. Because if you have found a new pair, you just place it in tuples with each of the previous ones (and each will give you 8 tuples). In this way you don't even need a second for loop, just the nested one.

[@robertbaindourov134]

Gauss figured out n(n+1)/2 for sum of a series. n(n-1)/2 is the binomial coefficient / combination formula, or triangular number.

[@anandmohansingh2390]

when nothing works, use hashmap

[@youssefmamdouh4987]

its simplified equation of n choose 2

[@ajitpalsingh606]

magic is sum of n numbers is n*(n-1)/2

[@punk5513]

Bro's timing is🔥🔥🔥

[@julianelmasry9556]

hashmap jutsu is key when dealing with pairs

[@anandailyasa2530]

Hi, I wonder what tools (hardware & software) does neetcode use for Drawing Explanation? anyone please help

[@testshubham]

Instead using two maps can use num of n natural numbers.

[@rangoliatti4890]

how do i get the code in java

[@MO-fg2cm]

Use your intuition and implement

[@deadlyecho]

I love counting problems, discrete mathematics ❤

[@AllThingsJS-ey6ww]

11th :)

[@Zenetz-le4mq]

He loves it we re doomed!

[@lan10ak]

1726 -> 1 + 7 = 2 + 6 Just coincidence

[@user_unknown04]

cool pull my boy

[@SandeepWithAI]

does questions like these are asked in real interviews where we have to derive a mathematical formula to solve it omg!...

[@motherofsuper]

Uhh, isn't permutations & combinations one of the most basic principles in high school maths anywhere in the world?

[@__amkhrjee__]

Respect 🫡

[@ajitpalsingh606]

i was able to reach till count should>=2

[@amanaryan7271]

nP2*4

[@chih-jenwu4992]

maybe we can use pairs = math.comb(cnt, 2) instead of (cnt * cnt(-1)) // 2

[@dekumidoriya-qi2is]

i solved it this way and i think it helps in lot of such problems with two pairs we have 8 combinations as the number of pairs increases the number of combinations of two pairs become 1 + 2 + 3 + .... + n - 1 so its just sum of (n - 1) natural numbers * 8 :) ==> (n)*(n - 1) * 4 hope this helps

[@maggiechen5430]

first