In a list of songs, the i-th 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 with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: [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: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Idea 1. Similar to Two Sum LT1, map with modular arithmetic
class Solution {
public int numPairsDivisibleBy60(int[] time) {
Map<Integer, Integer> record = new HashMap<>();
int count = 0;
for(int val: time) {
val = val%60;
count += record.getOrDefault((60 - val)%60, 0);
record.put(val, record.getOrDefault(val, 0) + 1);
}
return count;
}
}
array used as map
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] record = new int[60];
int count = 0;
for(int val: time) {
val = val%60;
count += record[(60 - val)%60];
++record[val];
}
return count;
}
}
Idea 1a. count pairs, preprose the array first
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] record = new int[60];
for(int val: time) {
val = val%60;
++record[val];
}
int count = 0;
if(record[0] > 0) {
count += record[0] * (record[0]-1)/2;
}
if(record[30] > 0) {
count += record[30] * (record[30]-1)/2;
}
for(int i = 1; i < 30; ++i) {
count += record[i]*record[60-i];
}
return count;
}
}
Note:
1 <= time.length <= 600001 <= time[i] <= 500