Problem Description
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.
Key Insights
- The sum of two durations is divisible by 60 if the remainders when divided by 60 complement each other (i.e., remainder A and remainder B such that A + B = 60).
- We can use a hash table (or array) to count occurrences of each possible remainder (0 to 59).
- Special cases include pairs where both songs have a remainder of 0, and pairs where both have a remainder of 30.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1) (constant space for the remainder counts since there are only 60 possible remainders)
Solution
To solve this problem, we can utilize a counting approach where we maintain an array to count the occurrences of each remainder when the song durations are divided by 60. We will then iterate through the time array, calculate the remainder for each duration, and find the complement remainder that would make the sum divisible by 60. For each song duration, we will look up how many times this complement has been seen so far, and add that to our count of valid pairs.