Pairs of Songs With Total Durations Divisible by 60: Remainder Counting

You are given a list of song durations in seconds. Your task is to count the number of pairs of songs whose total duration is divisible by 60. This is LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60.

Example: time = [30, 20, 150, 100, 40] returns 3 because the pairs (30, 150), (20, 100), and (20, 40) each sum to a multiple of 60.

Why this problem matters

At first this looks like a brute-force pairing problem: try every pair and check if their sum is divisible by 60. That works but costs O(n^2), which is too slow when n can be up to 60,000. The real challenge is recognizing that you do not need to compare every pair directly. You can reduce this to a single-pass counting problem using modular arithmetic.

The core technique here is the same complement-lookup pattern you see in Two Sum. In Two Sum, you check whether the complement target - nums[i] already exists in a hash map. In this problem, you check whether the complementary remainder (60 - r) % 60 already exists in a count array. The data structure is different (a fixed-size array of 60 slots instead of a general hash map), but the logic is identical: for each new element, look up how many previously-seen elements would form a valid pair with it, then record the current element for future lookups.

This pattern of remainder-based pairing shows up in many interview problems. Any time a problem asks about divisibility of sums, think about reducing values to their remainders first. This turns a numeric condition into a simpler equality condition: instead of asking "does a + b divide evenly by 60?" you ask "does r_a + r_b equal 0 or 60?" That simplification is what makes the O(n) solution possible.

The key insight

Two numbers sum to a multiple of 60 exactly when their remainders mod 60 sum to either 0 or 60. Since remainders are always in the range 0 to 59, the only way they can sum to a multiple of 60 is if they sum to exactly 0 or exactly 60. You can unify both cases with a single formula: for a song with remainder r, its complement is (60 - r) % 60.

When r is 0, the complement is (60 - 0) % 60 = 0. This correctly handles the case where two songs each have duration divisible by 60 (like 60 and 120). When r is 30, the complement is (60 - 30) % 60 = 30, which means two songs with remainder 30 can pair with each other. For any other remainder r, the complement is 60 - r, which is a different remainder.

This is a variation of the Two Sum pattern. In Two Sum, you maintain a hash map of values you have seen so far. Here, you maintain a count array of remainders you have seen so far. For each new song, you look up how many songs with the complementary remainder have already been processed, add that count to your result, and then record the current song's remainder. Because you only look backward (at songs already processed), you never double-count a pair.

The solution

def num_pairs_divisible_by_60(time):
    count = [0] * 60
    result = 0
    for t in time:
        r = t % 60
        complement = (60 - r) % 60
        result += count[complement]
        count[r] += 1
    return result

Here is what each piece does:

1. count = [0] * 60 creates a fixed-size array with 60 slots, one for each possible remainder (0 through 59). This is more efficient than a general hash map because the key space is bounded.

2. r = t % 60 computes the remainder of the current song duration when divided by 60. This is the only property that matters for divisibility.

3. complement = (60 - r) % 60 computes the remainder that would pair with r to form a sum divisible by 60. The outer % 60 handles the case where r is 0, ensuring the complement is also 0 rather than 60.

4. result += count[complement] adds the number of previously seen songs that have the complementary remainder. Each of those songs forms a valid pair with the current song.

5. count[r] += 1 records the current song's remainder for future lookups. This must come after the lookup to avoid counting a song as its own pair.

Visual walkthrough

The walkthrough processes each song left to right. At each step, the algorithm checks how many previously-seen songs have a complementary remainder, adds that count to the result, and then records the current remainder. After all five songs, the result is 3.

Complexity analysis

Time is O(n) because you iterate through the list once. For each element, the remainder computation, complement lookup, and count update are all O(1) operations.

Space is O(1) because the count array has exactly 60 elements regardless of the input size. Even though you are using extra memory, it does not grow with n. If you used a general hash map instead, the worst case would still be O(60) = O(1) since remainders are bounded.

The building blocks

1. Remainder pairing

The idea of reducing a divisibility check to a remainder check is a fundamental technique in number theory and competitive programming. When you need to determine if a + b is divisible by some constant k, compute a % k and b % k, then check if (a % k + b % k) % k == 0. This transforms a condition about potentially large numbers into a condition about small remainders.

In this problem, k = 60 and you need to find pairs. The remainder approach reduces 60,000 possible duration values down to just 60 possible remainder values. That compression is what makes the single-pass counting solution work. You are essentially grouping songs into 60 buckets by remainder, then counting how many cross-bucket (or same-bucket) pairs produce a sum of 0 mod 60.

This same technique applies to problems like Subarray Sums Divisible by K, where prefix sums and remainders combine to count valid subarrays. The core mechanic is always the same: reduce values to remainders, then reason about the remainders.

2. Single-pass counting (Two Sum variant)

The count-as-you-go pattern avoids the need to precompute all remainders before counting pairs. Instead of first building a full frequency table and then iterating again to count pairs, you do both in a single pass. For each element, you first check how many complements exist (using the counts accumulated so far), then you add the current element to the counts.

This ordering is critical. If you incremented count[r] before checking count[complement], you would risk counting a song as its own pair when r == complement (which happens for r = 0 and r = 30). By checking first and incrementing second, each pair is counted exactly once: the later element in the pair is the one that "finds" the earlier element.

This is the same principle behind the classic Two Sum solution. In Two Sum, you check if the complement exists in the hash map before inserting the current number. Here, you check the complement count before incrementing the current count. The data structure differs (array vs. hash map), but the algorithm skeleton is identical.

Edge cases

• All same remainder: e.g., [60, 120, 180] all have remainder 0. Every pair sums to a multiple of 60. The count is C(3,2) = 3. The single-pass approach handles this correctly because when processing the third element, count[0] is already 2, so it adds 2 (pairing with the first and second elements).

• No valid pairs: e.g., [31, 32, 33]. The remainders are 31, 32, and 33. No two of these sum to 60. The algorithm returns 0.

• Single element: e.g., [60]. There is only one song, so there are no pairs to form. The algorithm returns 0 because count[0] is still 0 when the first (and only) element is processed.

• Remainder 0 and 30: These are self-complementary remainders. A song with remainder 0 pairs with other songs that also have remainder 0. A song with remainder 30 pairs with other songs that also have remainder 30. The (60 - r) % 60 formula handles both cases correctly: (60 - 0) % 60 = 0 and (60 - 30) % 60 = 30.

• Large durations: e.g., [420, 480]. The remainders are 0 and 0, so the pair sums to 900, which is divisible by 60. The modulo operation correctly reduces these large values.

Common mistakes

1. Using 60 - r instead of (60 - r) % 60. When r is 0, 60 - r gives 60, which is out of bounds for the count array. The outer % 60 wraps this back to 0, which is the correct complement for remainder-0 songs.

2. Incrementing the count before checking the complement. If you write count[r] += 1 before result += count[complement], then when r == complement (i.e., r = 0 or r = 30), you count the current song as pairing with itself. Always check first, then increment.

3. Forgetting that remainders range from 0 to 59, not 1 to 60. The array needs exactly 60 slots indexed from 0 to 59. A song with duration exactly 60 has remainder 0, not 60.

4. Double-counting pairs with a two-pass approach. If you build a full frequency table and then iterate over all pairs of remainders, you might count (r1, r2) and (r2, r1) separately. The single-pass approach avoids this entirely.

From understanding to recall

You have seen the remainder counting technique and it makes sense. Compute r = t % 60, look up count[(60 - r) % 60], add to result, increment count[r]. Four lines inside the loop. Clean and efficient.

But in an interview, under pressure, it is easy to forget the outer % 60, or to increment the count before checking the complement, or to mix up the remainder pairing logic. These are not gaps in understanding. They are gaps in recall. You know the algorithm, but the details slip when you need them most.

Spaced repetition closes that gap. You practice writing the remainder counting loop from scratch at increasing intervals. After a few rounds, the formula (60 - r) % 60 is automatic. You do not think about whether you need the outer modulo. You just write it. The order of operations (check, then increment) becomes muscle memory, not a decision you make under stress.

The complement-lookup pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Two Sum - Same pattern of complement lookup in a hash map
• Subarray Sum Equals K - Counting with hash maps and prefix sums
• Contains Duplicate II - Hash map with index tracking for proximity constraints

CodeBricks breaks the pairs of songs with total durations divisible by 60 problem into its remainder pairing and single-pass counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a remainder-based counting question shows up in your interview, you do not think about it. You just write it.