# 1009. Complement of Base 10 Integer

You are given a list of songs where the ith song has a duration of `time[i]` seconds.

Return  the number of pairs of songs for which their total duration in seconds is divisible by  `60`. Formally, we want the number of indices `i``j` such that `i < j` with `(time[i] + time[j]) % 60 == 0`.

Example 1:

``````Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
``````

Example 2:

``````Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
``````

Constraints:

• `1 <= time.length <= 6 * 104`
• `1 <= time[i] <= 500`

``````class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
int res = 0;
unordered_set<int> visited;
unordered_map<int, int> timeCnt;
for (int t : time) ++timeCnt[t % 60];
for (auto &a : timeCnt) {
if (visited.count(a.first)) continue;
if (a.first % 60 == 0 || a.first == 30) {
res += (a.second - 1) * a.second / 2;
} else {
int target = 60 - a.first;
if (!timeCnt.count(target)) continue;
res += a.second * timeCnt[target];
visited.insert(target);
}
visited.insert(a.first);
}
return res;
}
};
``````

``````class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
int res = 0;
vector<int> cnt(60);
for (int t : time) {
res += cnt[(600 - t) % 60];
++cnt[t % 60];
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1010

Two Sum

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/discuss/256738/JavaC%2B%2BPython-Two-Sum-with-K-60

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/discuss/256726/JavaPython-3-O(n)-code-w-comment-similar-to-Two-Sum

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation