Chương trình tìm bộ bốn có tích bằng nhau trong Python

Mô tả bài toán

Cho mảng nums các số dương duy nhất. Đếm số bộ bốn (a,b,c,d) phân biệt sao cho a*b = c*d.

Ví dụ

nums = [2,3,4,6] -> 8 bộ: (2,6,3,4), (2,6,4,3), (6,2,3,4), (6,2,4,3), (3,4,2,6), (4,3,2,6), (3,4,6,2), (4,3,6,2).

Giải thuật

1. Đếm tần suất từng tích nums[i]*nums[j] (i < j) vào dic.
2. Với mỗi tần suất v >= 2: số bộ bốn = (v-1)/2 * (8 + 8*(v-1)) = 4*v*(v-1).
3. Tổng cộng tất cả.

Triển khai Python

from collections import defaultdict

def solve(nums):
    dic = defaultdict(int)
    ans = 0
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            dic[nums[i] * nums[j]] += 1
    for v in dic.values():
        if v == 1:
            continue
        v -= 1
        s = (v / 2) * (8 + 8 * v)
        ans += s
    return int(ans)

nums = [3, 4, 6, 2]
print(solve(nums))

Đầu vào

[3,4,6,2]

Đầu ra

8