Chương trình Python đếm số quadruple tích cặp đầu cuối bằng nhau

Cho danh sách nums các số dương duy nhất. Đếm số quadruple (a, b, c, d) với a, b, c, d distinct (khác nhau hoàn toàn) sao cho a * b = c * d.

Ví dụ

nums = [3, 6, 4, 8]
Output: 8
Quadruples: [3,8,6,4], [3,8,4,6], [8,3,6,4], [8,3,4,6], [6,4,3,8], [4,6,3,8], [6,4,8,3], [4,6,8,3]
Tất cả có tích = 24.

Thuật toán: Đếm cặp theo tích

1. Duyệt mọi cặp (i, j) với i < j, tính tích x = nums[i] * nums[j].
2. Đếm tần suất mỗi tích: count[x]++.
3. Với mỗi tích có count = c, số cách chọn 2 cặp khác nhau = C(c, 2) = c * (c-1) / 2.
4. Mỗi lần chọn 2 cặp tạo ra 8 quadruple (hoán vị 2 cặp × 2! thứ tự trong cặp × 2! thứ tự 2 cặp).
5. Tổng = sum(c * (c-1) * 4).

Code Python

def solve(nums):
    count = {}
    n = len(nums)
    
    # Đếm tần suất mỗi tích
    for i in range(n):
        for j in range(i + 1, n):
            x = nums[i] * nums[j]
            count[x] = count.get(x, 0) + 1
    
    # Tính tổng quadruple
    ret = 0
    for c in count.values():
        ret += c * (c - 1)  # c*(c-1) = 2 * C(c,2)
    
    return ret * 4  # mỗi cặp cặp cho 8 quadruple, nhưng c*(c-1) đã tính ordered pairs

# Test
print(solve([3, 6, 4, 8]))  # 8
print(solve([1, 2, 3, 4, 6, 8, 12]))  # More

Giải thích công thức

• Cặp (a,b) và (c,d) cho tích x. Số cặp = c.
• Số cách chọn 2 cặp khác nhau (thứ tự cặp quan trọng vì (a,b) vs (c,d) khác vị trí): P(c, 2) = c * (c-1).
• Mỗi cặp (a,b) có 2 hoán vị: (a,b) và (b,a). Tương tự (c,d).
• Tuy nhiên: c * (c-1) đã đếm ordered pairs của cặp. Mỗi ordered pair cho 4 quadruple: (a,b,c,d), (b,a,c,d), (a,b,d,c), (b,a,d,c).
• → Tổng = c * (c-1) * 4.

Trace ví dụ [3,6,4,8]

Pairs & products:
(3,6)=18, (3,4)=12, (3,8)=24
(6,4)=24, (6,8)=48
(4,8)=32

Count: {18:1, 12:1, 24:2, 48:1, 32:1}
Chỉ 24 có count=2
ret = 2*1 = 2
result = 2 * 4 = 8 ✓

Độ phức tạp

• Thời gian: O(n²) - duyệt mọi cặp.
• Không gian: O(n²) worst-case cho dictionary count (số tích khác nhau).
• Tối ưu: không thể tốt hơn O(n²) vì output size có thể O(n²).

Điều kiện "distinct elements"

Đề bài yêu cầu a,b,c,d distinct. Với nums distinct, 2 cặp cho cùng tích tự động đảm bảo 4 phần tử distinct (nếu share 1 phần tử → 2 cặp cùng 1 số → tích khác trừ trường hợp 0, nhưng nums dương).