336. Pairs of Songs With Total Durations Divisible by 60
Medium
Complement Remainder Counting
Hashing
Problem
You are given an array time where time[i] is the duration of a song in seconds. Return the number of index pairs (i, j), with i less than j, for which time[i] + time[j] is divisible by 60.
Examples
Example 1
Input: [30,20,150,100,40]
Output: 3
Example 2
Input: [60,60,60]
Output: 3
Example 3
Input: [10,50]
Output: 1
Constraints
� 1 <= time.length <= 60000
� 1 <= time[i] <= 500
Hints
?? Only each duration's remainder modulo 60 matters.
?? A remainder r needs a previous remainder (60 - r) modulo 60.
?? Remainders 0 and 30 complement themselves.
Expected Complexity
Time: O(n)
Space: O(1)
Follow-up
Can you count valid pairs online in one pass using an array of exactly 60 counters?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[30,20,150,100,40]Expected
3