Pairs of Songs With Total Durations Divisible by 60
Asked at Atlassian
Problem
Given a list of song durations, find how many pairs of songs have total duration divisible by 60. Each pair (i, j) where i < j counts once. The solution must handle large inputs efficiently using modular arithmetic.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | MEDIUM | View all Atlassian questions → |
How to Think About It
Compute remainder of each duration when divided by 60
Use hash map to count occurrences of each remainder
For remainder r, find complement (60 - r) % 60 in the map
Handle special case where remainder is 0 (pairs with other 0s)
Count pairs incrementally while iterating for O(n) solution
Optimal Approach
Use modular arithmetic to track remainders when dividing durations by 60. Maintain a count of each remainder seen so far. For each new duration with remainder r, the complement is (60 - r) % 60. Add the count of that complement to the result. Increment the count of the current remainder. This yields O(n) time with O(1) space since remainders range from 0 to 59.
What Trips People Up in Real Interviews
Clarify that remainder 0 pairs with remainder 0, not 60
Explain why (60 - r) % 60 handles both r=0 and r=30 cases
Discuss the O(n) time and O(1) space solution using counting
Mention edge case: all songs exactly 60 minutes long
Consider how to extend to divisibility by arbitrary number
Solution Code
def numPairsDivisibleBy60(time):
count = [0] * 60
result = 0
for t in time:
r = t % 60
complement = (60 - r) % 60
result += count[complement]
count[r] += 1
return resultFrequently Asked Questions
What is the Pairs of Songs With Total Durations Divisible by 60 problem?
Given a list of song durations, find how many pairs of songs have total duration divisible by 60. Each pair (i, j) where i < j counts once. The solution must handle large inputs efficiently using modular arithmetic.
How do you solve Pairs of Songs With Total Durations Divisible by 60?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Pairs of Songs With Total Durations Divisible by 60?
Pairs of Songs With Total Durations Divisible by 60 is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Pairs of Songs With Total Durations Divisible by 60?
- Clarify that remainder 0 pairs with remainder 0, not 60
- Explain why (60 - r) % 60 handles both r=0 and r=30 cases
- Discuss the O(n) time and O(1) space solution using counting
- Mention edge case: all songs exactly 60 minutes long
- Consider how to extend to divisibility by arbitrary number