Problem Description

You have a playlist of songs where each song has a specific duration in seconds. The task is to find how many pairs of songs can be combined such that their total duration is exactly divisible by 60 seconds.

Given an array time where time[i] represents the duration of the i-th song in seconds, you need to count all valid pairs (i, j) where:

• i < j (to avoid counting the same pair twice and pairing a song with itself)
• (time[i] + time[j]) % 60 == 0 (the sum of their durations is divisible by 60)

For example, if you have songs with durations [30, 20, 150, 100, 40]:

• Songs at indices 0 and 2: 30 + 150 = 180, which is divisible by 60 ✓
• Songs at indices 1 and 3: 20 + 100 = 120, which is divisible by 60 ✓
• Songs at indices 1 and 4: 20 + 40 = 60, which is divisible by 60 ✓

The answer would be 3 pairs.

The solution uses modular arithmetic to optimize the counting. Since we only care about divisibility by 60, we can work with remainders when dividing by 60. Two numbers sum to a multiple of 60 if their remainders sum to either 0 or 60. The code counts frequencies of each remainder value and calculates valid pairs based on complementary remainders.

Intuition

The key insight is recognizing that we don't need to check every possible pair of songs, which would take O(n²) time. Instead, we can use the properties of modular arithmetic to solve this more efficiently.

When we want to check if two numbers sum to a multiple of 60, we only care about their remainders when divided by 60. For example, 150 and 30 have the same effect as 90 and 30 when checking divisibility by 60, because 150 % 60 = 30 and 90 % 60 = 30.

This leads us to think: for a song with duration that gives remainder r when divided by 60, what remainder should its pair have? If the first song has remainder r, then the second song must have remainder 60 - r for their sum to be divisible by 60. For instance:

• A song with remainder 20 pairs with songs having remainder 40 (since 20 + 40 = 60)
• A song with remainder 15 pairs with songs having remainder 45 (since 15 + 45 = 60)

There are two special cases to handle:

1. When remainder is 0: These songs pair with other songs that also have remainder 0 (since 0 + 0 = 0, which is divisible by 60)
2. When remainder is 30: These songs pair with other songs that also have remainder 30 (since 30 + 30 = 60)

For these special cases, we're choosing 2 songs from the same group, so we use the combination formula n * (n - 1) / 2 to count pairs without repetition.

By counting the frequency of each remainder value from 0 to 59, we can quickly calculate the total number of valid pairs by multiplying the counts of complementary remainders together.

Solution Approach

The solution uses a hash map (Counter) to track the frequency of each remainder value, then calculates the number of valid pairs based on these frequencies.

Step 1: Calculate remainders and count frequencies

cnt = Counter(t % 60 for t in time)

We iterate through all songs and calculate t % 60 for each duration t. The Counter creates a frequency map where the key is the remainder (0-59) and the value is how many songs have that remainder.

Step 2: Count pairs with complementary remainders

ans = sum(cnt[x] * cnt[60 - x] for x in range(1, 30))

For remainders from 1 to 29, we pair each remainder x with its complement 60 - x. For example:

• Remainder 1 pairs with remainder 59
• Remainder 2 pairs with remainder 58
• Remainder 29 pairs with remainder 31

The number of pairs is cnt[x] * cnt[60 - x] because each song with remainder x can pair with any song having remainder 60 - x.

We only iterate from 1 to 29 to avoid counting each pair twice (since remainder 1 with 59 is the same as remainder 59 with 1).

Step 3: Handle special case for remainder 0

ans += cnt[0] * (cnt[0] - 1) // 2

Songs with remainder 0 pair with other songs having remainder 0. Since we're selecting 2 songs from the same group of cnt[0] songs, we use the combination formula C(n, 2) = n * (n - 1) / 2.

Step 4: Handle special case for remainder 30

ans += cnt[30] * (cnt[30] - 1) // 2

Similarly, songs with remainder 30 pair with other songs having remainder 30 (since 30 + 30 = 60). We apply the same combination formula.

The time complexity is O(n) where n is the number of songs, and space complexity is O(1) since we store at most 60 different remainder values.

Example Walkthrough

Let's walk through a small example with time = [30, 20, 150, 100, 40].

Step 1: Calculate remainders and build frequency map

For each song duration, we calculate duration % 60:

• 30 % 60 = 30
• 20 % 60 = 20
• 150 % 60 = 30
• 100 % 60 = 40
• 40 % 60 = 40

Our frequency counter becomes:

• cnt[20] = 1 (one song with remainder 20)
• cnt[30] = 2 (two songs with remainder 30)
• cnt[40] = 2 (two songs with remainder 40)
• All other remainders have count 0

Step 2: Count pairs with complementary remainders (1 to 29)

We iterate through remainders 1 to 29 and multiply counts with their complements:

• For x = 20: complement is 60 - 20 = 40
  • Pairs = cnt[20] * cnt[40] = 1 * 2 = 2
  • This accounts for songs at indices (1,3) and (1,4)
• For all other values 1-29: either cnt[x] = 0 or cnt[60-x] = 0, contributing 0 pairs

Running total after this step: ans = 2

Step 3: Handle remainder 0

cnt[0] = 0, so this contributes 0 * (0 - 1) / 2 = 0 pairs.

Running total: ans = 2

Step 4: Handle remainder 30

cnt[30] = 2, so songs with remainder 30 can pair with each other.

• Pairs = 2 * (2 - 1) / 2 = 1
• This accounts for the pair at indices (0,2)

Final total: ans = 2 + 1 = 3

The three valid pairs are:

1. Indices (0,2): 30 + 150 = 180 (divisible by 60)
2. Indices (1,3): 20 + 100 = 120 (divisible by 60)
3. Indices (1,4): 20 + 40 = 60 (divisible by 60)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main parts:

1. Creating a Counter object from the list of remainders when each time value is divided by 60 - this requires iterating through all n elements in the time list, taking O(n) time.
2. Computing the answer by iterating through a fixed range from 1 to 29 (constant time O(1)), plus two additional constant-time operations for special cases at indices 0 and 30.

Since the iteration in step 2 is over a constant range (29 iterations), it contributes O(1) to the overall complexity. Therefore, the total time complexity is O(n) + O(1) = O(n).

Space Complexity: O(1)

The Counter object cnt stores the frequency of remainders when dividing by 60. Since the remainder of any number divided by 60 can only be in the range [0, 59], the Counter will have at most 60 unique keys. This means the space used by the Counter is bounded by a constant (60), regardless of the input size n. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Double Counting Pairs

Pitfall: A common mistake is iterating through all remainders from 0 to 59 and counting pairs, which results in counting each pair twice.

# WRONG: This counts each pair twice
result = 0
for remainder in range(60):
    complement = (60 - remainder) % 60
    result += remainder_count[remainder] * remainder_count[complement]
return result // 2  # Dividing by 2 doesn't fix all cases

Why it's wrong: When you process remainder 1, you count pairs with remainder 59. Later, when processing remainder 59, you count the same pairs again. Additionally, the special cases (remainder 0 and 30) would be incorrectly handled.

Solution: Only iterate through remainders 1 to 29, and handle special cases separately:

# CORRECT: Process each unique pair once
for remainder in range(1, 30):
    complement = 60 - remainder
    result += remainder_count[remainder] * remainder_count[complement]

2. Incorrect Handling of Remainder 0

Pitfall: Treating remainder 0 like other remainders and trying to find its complement.

# WRONG: Trying to pair remainder 0 with remainder 60
complement = 60 - 0  # This gives 60, which doesn't exist as a remainder
result += remainder_count[0] * remainder_count[60]  # KeyError or 0

Why it's wrong: The remainder when dividing by 60 can only be 0-59. There's no remainder 60. Songs with remainder 0 should pair with other songs having remainder 0.

Solution: Use combination formula for self-pairing:

# CORRECT: Songs with remainder 0 pair with each other
result += remainder_count[0] * (remainder_count[0] - 1) // 2

3. Forgetting the Remainder 30 Special Case

Pitfall: Not recognizing that remainder 30 is self-complementary (30 + 30 = 60).

# WRONG: Only handling remainder 0 as special case
for remainder in range(1, 30):
    result += remainder_count[remainder] * remainder_count[60 - remainder]
result += remainder_count[0] * (remainder_count[0] - 1) // 2
# Missing remainder 30 handling!

Why it's wrong: Remainder 30 pairs with itself to make 60, similar to how remainder 0 pairs with itself to make 0 (which is divisible by 60).

Solution: Apply the same combination formula to remainder 30:

# CORRECT: Handle both special cases
result += remainder_count[0] * (remainder_count[0] - 1) // 2
result += remainder_count[30] * (remainder_count[30] - 1) // 2

4. Using Wrong Combination Formula

Pitfall: Using multiplication instead of combination for self-pairing cases.

# WRONG: This counts pairing a song with itself
result += remainder_count[0] * remainder_count[0]

Why it's wrong: This would count invalid pairs like (i, i) and count valid pairs twice.

Solution: Use the proper combination formula C(n, 2):

# CORRECT: Choose 2 songs from n songs
result += remainder_count[0] * (remainder_count[0] - 1) // 2