590. Pairs of Songs With Total Durations Divisible by 60
You have a playlist where song i runs for time[i] seconds. A pair of songs is loopable if their combined length is an exact number of minutes — that is, (time[i] + time[j]) % 60 == 0.
Your function receives the integer array time and must return a single integer: the number of index pairs (i, j) with i < j whose durations sum to a multiple of 60.
Note that the count can exceed the range of a 32-bit integer's comfort zone on large inputs — count carefully.
Example 1:
Input: time = [30, 20, 150, 100, 40]
Output: 3
Explanation: Three pairs hit a whole minute: 30 + 150 = 180, 20 + 100 = 120, and 20 + 40 = 60.
Example 2:
Input: time = [60, 60, 60]
Output: 3
Explanation: Every one of the three possible pairs sums to 120, so all of them count.
Constraints:
- 1 ≤ time.length ≤ 6 * 10⁴
- 1 ≤ time[i] ≤ 500
Hints:
Only remainders mod 60 matter: a pair works exactly when the two remainders add to 0 or 60. Reduce every duration to time[i] % 60 first.
Scan once with a table count[0..59] of remainders seen so far. For the current remainder r, the partners already seen are those with remainder (60 - r) % 60 — add that count, then record r. The remainders 0 and 30 pair with themselves, and the check-before-insert order handles them for free.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: time = [30, 20, 150, 100, 40]
Expected output: 3