Leetcode 923 3Sum With Multiplicity

Given an array of integer, we want to find the number of tuple (i,j,k) such that i < j < k and A[i] + A[j] + A[k] == target.\ As the answer can be very large, return it modulo 10^9 + 7. Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8 Output: 20 Explanation: Enumerating by the values (A[i], A[j], A[k]): (1, 2, 5) occurs 8 times; (1, 3, 4) occurs 8 times; (2, 2, 4) occurs 2 times; (2, 3, 3) occurs 2 times.

Input: A = [1,1,2,2,2,2], target = 5 Output: 12 Explanation: A[i] = 1, A[j] = A[k] = 2 occurs 12 times: We choose one 1 from [1,1] in 2 ways, and two 2s from [2,2,2,2] in 6 ways.

Note:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

This problem is related to 3sum; we need to iterate through two index i and j to find the k such that a[k] == target – a[i] – a[j]. But we also need to record the frequency of each number for calculating the number of ways a specific (A[i],A[j], A[k]) can appear. EG: Input: A = [1,1,2,2,2,2], target = 5. 5 = 1 + 2 + 2 and there are 2 ways to choose 1 and 4 ways to choose 2. 2 choose 1 * 4 choose 2 = 2 * ( 4 + 3)/2 = 2 * 6.

Step 1: \ Init an array freq of size 100 (since 0 <= A[i] <= 100) and iterate through A

for num in A:
    freq[num] += 1

Step2: Use a nested for loop to iterate through all possible i, j(from 10 to 100) such that k = target – i – j We need to make sure that 0 <=i <= 100, 0 <= j <= 100 and 0 <=k <= 100 and also i, j and k are in A. And also i <= j <= k Else we got duplicates. (i = 1, j = 2, k = 4, t = 7 and i = 2, j = 1, k = 4 t = 7 will double count the same number of combinations.) \

Once we have three number i,j,k in A and i + j + k = target, we have found a tuple. We don’t have to reconstruct the tuple since we only care about how many tuples there are that satisfy i + j + k = target. \ To find how many ways to construct i + j + k = target, we need to make several cases here: \

  1. i == j == k: \ total += freq[i] choose 3. == freq[i] * (freq[i] -1) * (freq[i] – 2) / 6\ \
  2. i = j: \ total +=freq[i] choose 2 * freq[k] choose 1 == freq[i] * (freq[i] – 1) //2 * freq[k]\ \

  3. j = k : \ total +=freq[h] choose 2 * freq[i] choose 1 == freq[j] * (freq[j] – 1) //2 * freq[i]\ \

  4. i != j != k:\ total +=freq[i] * freq[j] * freq[k]\

Every admissible i, j, k will fall into these four cases. And we will add that to total count.

for i in range(0, target + 1):
    for j in range(0, target + 1):
        k = target - i - j
        if (freq[i] == 0 or freq[j] == 0 or freq[k] == 0): continue
        if k < 0 or k > 100 : continue
        try out the four conditions aboce

We need to iterate through i and j till they hit the 100 since [0, 100] are all permissible values In python that means range(101) The benefit of working with frequency appears here. We don’t have to deal with duplicates.

The running time is O(n) since the nested for loop runs a constant amount of time, the only linear term will come from constructing the frequency array.

A short review of n choose k.

n choose k is choosing k element from n, regardless of the order. The formula is $\dfrac{n!}{k! ( n – k)!}$ The nominator is n!, the number of permutation(different ways to arrange n numbers). The denominator contains k! and (n – k)!. $\dfrac{n!}{(n – k)!} $ is the number of ways arrange k element choosing from n. Since the order doesn’t matter and there are k! ways to arrange k element, we divide the result by k!.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax