#1010

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Pairs of Songs With Total Durations Divisible by 60

Calculate the number of song pairs whose total durations sum to a multiple of 60 using array scanning and hash lookups.

Problem Statement

You are given an array of integers where each element represents the duration in seconds of a song. Your task is to count all unique pairs of songs such that the sum of their durations is divisible by 60.

Formally, return the number of index pairs (i, j) with i < j where (time[i] + time[j]) % 60 == 0. For example, given time = [30,20,150,100,40], the correct output is 3, corresponding to pairs (30,150), (20,100), and (20,40).

Examples

Example 1

Input: time = [30,20,150,100,40]

Output: 3

Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180 (time[1] = 20, time[3] = 100): total duration 120 (time[1] = 20, time[4] = 40): total duration 60

Example 2

Input: time = [60,60,60]

Output: 3

All three pairs have a total duration of 120, which is divisible by 60.

Constraints

1 <= time.length <= 6 * 104
1 <= time[i] <= 500

Solution Approach

Use a remainder hash table

Track the count of each song duration modulo 60 in a hash table. For each song, compute (60 - time[i] % 60) % 60 and add the count of that remainder from previous songs.

Single pass iteration

Iterate through the time array once, updating the hash table and counting valid pairs simultaneously. This ensures O(n) time complexity without nested loops.

Handle edge cases

Specially handle songs where time[i] % 60 == 0 because they pair with other zero-remainder songs. Ensure pairs are only counted once to avoid duplicates.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for scanning the array once. Space complexity is O(60) = O(1) due to storing counts for each possible remainder modulo 60.

What Interviewers Usually Probe

Looking for a hash map or remainder counting solution
Mentions modulo arithmetic or pair summing
Checks for handling edge cases with zero or multiple of 60 durations

Common Pitfalls or Variants

Common pitfalls

Double-counting pairs when scanning array
Ignoring songs with remainder 0 or 30 specially
Using nested loops leading to O(n^2) time instead of hash approach

Follow-up variants

Count pairs divisible by k instead of 60
Return the actual index pairs rather than the count
Handle streaming input of song durations

FAQ

How does the modulo 60 pattern help in counting song pairs?

It reduces the problem to tracking remainders of durations, so for each song you only need to check for a complementary remainder that sums to 60.

What if a song duration is exactly divisible by 60?

Songs divisible by 60 pair with other songs divisible by 60. The solution handles this by using remainder 0 in the hash table.

Can this approach handle large arrays efficiently?

Yes, because it scans the array once and uses only a fixed-size hash table for remainders, achieving O(n) time complexity.

Is it necessary to store all song pairs?

No, only counting is needed. Storing pairs increases space usage and is unnecessary for the problem requirements.

What pattern does this problem follow in GhostInterview terms?

It follows the 'Array scanning plus hash lookup' pattern, using remainders to map pairs efficiently without nested iteration.

terminal

Solution

Solution 1: Math + Counting

If the sum of a pair $(a, b)$ is divisible by $60$, i.e., $(a + b) \bmod 60 = 0$, then $(a \bmod 60 + b \bmod 60) \bmod 60 = 0$. Let $x = a \bmod 60$ and $y = b \bmod 60$, then $(x + y) \bmod 60 = 0$, which means $y = (60 - x) \bmod 60$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for x in time:
            x %= 60
            y = (60 - x) % 60
            ans += cnt[y]
            cnt[x] += 1
        return ans

Continue Practicing

#992 subarrays with k different integers #1054 distant barcodes #1090 largest values from labels