Pairs of Songs With Total Durations Divisible by 60

Pairs of Songs With Total Durations Divisible by 60

What is this problem about?

The Pairs of Songs With Total Durations Divisible by 60 problem asks you to count pairs (i, j) where i < j and (time[i] + time[j]) % 60 == 0. This is the modular complement pair counting problem. The array, hash table, and counting interview pattern is demonstrated.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Amazon, Google, and many others ask this because it's a direct application of the "two sum with modular arithmetic" pattern. Count durations modulo 60 and look for complementary remainders. It tests whether candidates can adapt two-sum to modular arithmetic.

Algorithmic pattern used

Modular complement counting. For each song time t: compute r = t % 60. The complement needed = (60 - r) % 60. Count how many previous songs had remainder (60-r)%60. Add to result. Update the frequency array at index r.

Example explanation

times=[30,20,150,100,40]. Mod 60: [30,20,30,40,40].

• 30: complement=30. count[30]=0. count[30]+=1. Pairs=0.
• 20: complement=40. count[40]=0. count[20]+=1. Pairs=0.
• 30: complement=30. count[30]=1. Pairs+=1. count[30]+=1.
• 40: complement=20. count[20]=1. Pairs+=1. count[40]+=1.
• 40: complement=20. count[20]=1. Pairs+=1. count[40]+=1. Total = 3.

Common mistakes candidates make

• Using (60-r)%60 instead of just 60-r (forgetting to handle r=0 case where complement=60, not 0).
• Processing in nested loops O(n²) instead of hash map O(n).
• Off-by-one: query count[complement] BEFORE updating count[r].
• Using r+complement=60 instead of (r+complement)%60==0.

Interview preparation tip

Modular complement pair problems are extensions of two-sum to modular arithmetic. The pattern: for each element with remainder r, its complement has remainder (m-r)%m. A frequency array of size m gives O(1) lookup. Practice this for different moduli: "pairs summing to divisible by 7," "pairs of strings with length divisible by k." The (m-r)%m formula handles the r=0 case cleanly.