Cặp Bài Hát Tổng Thời Lượng Chia Hết Cho 60 (Pairs of Songs Divisible by 60) Trong Python

Cho mảng time độ dài bài hát (giây). Đếm số cặp (i, j) với i < j sao cho (time[i] + time[j]) % 60 == 0.

Ví dụ: [30,20,150,100,40] → 3 cặp: (30,150)=180, (20,100)=120, (20,40)=60.

Thuật toán (Hash Map remainder)

1. Đếm tần suất phần dư khi chia 60: remainder[count] = số lượng bài hát có time % 60 == count
2. Duyệt từng bài hát t:
   • r = t % 60
   • Cần phần dư bổ sung: need = (60 - r) % 60
   • Cộng vào kết quả: ans += remainder[need]
   • Cập nhật: remainder[r] += 1

Ví dụ (Python)

from collections import defaultdict

class Solution(object):
    def numPairsDivisibleBy60(self, time):
        remainder = defaultdict(int)
        ans = 0
        
        for t in time:
            r = t % 60
            need = (60 - r) % 60
            ans += remainder[need]
            remainder[r] += 1
        
        return ans

ob1 = Solution()
print(ob1.numPairsDivisibleBy60([30,20,150,100,40]))  # 3
print(ob1.numPairsDivisibleBy60([60,60,60]))          # 3 (C(3,2))
print(ob1.numPairsDivisibleBy60([30,30,30]))          # 3 (30+30=60)

Giải thích

• r = 0: cần cặp cũng r = 0 (0+0=0)
• r = 30: cần cặp r = 30 (30+30=60)
• Khác: r cần 60-r

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(1) (chỉ 60 phần dư có thể)

Đầu vào / Đầu ra

Input:  [30,20,150,100,40]
Output: 3