1010. Pairs of Songs With Total Durations Divisible by 60
Tags:
Medium
Skills:
Combination
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu đếm số cặp bài hát sao cho tổng thời lượng của hai bài chia hết cho 60. Cụ thể với mối cặp i < j, cần kiểm tra (time[i] + time[j]) % 60 = 0;
Approach
Nếu bạn loop từ x = 1 đến x = 59, thì mỗi cặp (x, 60-x) sẽ bị đếm hai lần:
x = 10, 60-x = 50 → đếm cặp (10,50)x = 50, 60-x = 10 → lại đếm cặp (50,10)Để tránh đếm trùng, chỉ cần xét mỗi cặp một lần, nên chỉ loop từ x = 1 đến x = 29 (vì 60-29=31, sau đó sẽ lặp lại).
x = 0 và x = 30, x trùng với 60-x (vì 60-0=0, 60-30=30).cnt* cnt[60-x] sẽ thành cnt*cnt hoặc cnt*cnt, nhưng điều này không đúng vì sẽ đếm cả cặp (a,a) là không hợp lệ (không có bài hát ghép với chính nó).cnt* (cnt- 1) / 2 (chọn 2 bài trong nhóm).Solution - Đếm trước, tính sau
1function numPairsDivisibleBy60(time: number[]): number {
2 const cnt: number[] = new Array(60).fill(0);
3 for(const t of time) {
4 cnt[t % 60]++;
5 }
6 let ans = 0;
7 for(let x = 1; x < 30; x++) {
8 ans += cnt[x] * cnt[60 - x];
9 }
10 ans += (cnt[0] * (cnt[0] - 1)) / 2;
11 ans += (cnt[30] * (cnt[30] - 1)) / 2;
12 return ans
13};Solution - One-pass
1function numPairsDivisibleBy60(time: number[]): number {
2 const cnt: number[] = new Array(60).fill(0);
3 let ans = 0;
4 for(let x of time) {
5 x = x % 60;
6 const y = (60 - x) % 60;
7 ans += cnt[y];
8 cnt[y]++;
9 }
10 return ans;
11};