Leetcode 1010. Pairs of Songs With Total Durations Divisible by 60

Problem Explanation

We are given a list of song durations in seconds and we want to find all pairs of song durations whose sum is divisible by 60. Essentially, we are to find combinations of pairs (i , j) such that time[i] + time[j] mod 60 equals 0 and we only count a pairing if i is less than j.

For instance, given the list of song durations [30, 20, 150, 100, 40], we get three pairs whose sum of durations is divisible by 60: (30, 150), (20, 100), (20, 40). Hence the output in this case will be 3.

Solution Approach

The approach that can be used to solve this problem combines the use of a frequency counter data structure and elementary number theory. Essentially, we observe that for a number to be divisible by 60, its remainder when divided by 60 must be 0. And for two numbers, a and b, to sum up to a number divisible by 60, the sum of their remainders when each is divided by 60 must either be 0 (if a and b are both divisible by 60) or 60 (if neither a nor b is divisible by 60).

Given these observations, we can find the modulus 60 of each duration and keep track of the count of these moduli. Then for each modulus, if it's not 0, we add the minimum value between its count and the count of its complement (60 minus the modulus) to a running total that represents the number of pairs. If the modulus is zero, however, we add to the running total a combination of the count taken two at a time (since each pair uses two songs). The count operation will give us the corresponding matching pairs that sum to a number divisible by 60 after taking mod 60.

ASCII Illustration

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

1
2
3(1) Modulus 60 count: [0: 0, 20: 2, 30: 1, 40: 1, 50: 1]
4(2) Pairs: [(30, 150), (20, 100), (20, 40)]
5(3) Return the count of pairs: 3

Java Solution

1
2java
3class Solution {
4  public int numPairsDivisibleBy60(int[] time) {
5    int[] remainderCounts = new int[60];
6    int pairCount = 0;
7    for (int t : time) {
8      int remainder = t % 60;
9      pairCount += remainderCounts[(60 - remainder) % 60];
10      remainderCounts[remainder] ++;
11    }
12    return pairCount;
13  }
14}

C++ Solution

1
2cpp
3class Solution {
4public:
5  int numPairsDivisibleBy60(vector<int>& time) {
6    vector<int> remainders(60);
7    int count = 0;
8    for (int t : time) {
9        t %= 60;
10        count += remainders[(60 - t) % 60];
11        ++remainders[t];
12    }
13    return count;
14  }
15};

Python Solution

1
2python
3class Solution:
4  def numPairsDivisibleBy60(self, time: List[int]) -> int:
5    remainders = [0] * 60
6    pairCount = 0
7    for t in time:
8      remainder = t % 60;
9      pairCount += remainders[(60 - remainder) % 60]
10      remainders[remainder] += 1
11    return pairCount

JavaScript Solution

1
2javascript
3var numPairsDivisibleBy60 = function(time) {
4    let remainders = new Array(60).fill(0);
5    let count = 0;
6
7    for (let t of time) {
8        t %= 60;
9        count += remainders[(60 - t) % 60];
10        remainders[t]++;
11    }
12
13    return count;
14};

C# Solution

1
2csharp
3public class Solution {
4    public int NumPairsDivisibleBy60(int[] time) {
5        int[] reminderCounts = new int[60];
6        int pairCount = 0;
7        foreach (int t in time) {
8            int reminder = t % 60;
9            pairCount += reminderCounts[(60 - reminder) % 60];
10            reminderCounts[reminder]++;
11        }
12        return pairCount;
13    }
14}

In all the solutions, we initialize an array of 60 zeros to count the remainders, and for each song duration in the time list, we find its modulus 60 and add the count of its matching pair from the count array to a running total count which we return as the final answer. The index that matches a remainder r is (60 - r) % 60.## Rust Solution

1
2rust
3pub fn num_pairs_divisible_by60(time: Vec<i32>) -> i32 {
4    let mut remainders = vec![0; 60];
5    let mut count = 0;
6
7    for t in time.iter() {
8        let remainder = t % 60;
9        count += remainders[((60 - remainder) % 60) as usize];
10        remainders[remainder as usize] += 1;
11    }
12
13    count
14}

Swift Solution

1
2swift
3class Solution {
4    func numPairsDivisibleBy60(_ time: [Int]) -> Int {
5        var remainders = Array(repeating: 0, count: 60)
6        var count = 0
7        
8        for t in time {
9            let remainder = t % 60
10            count += remainders[(60 - remainder) % 60]
11            remainders[remainder] += 1
12        }
13
14        return count
15    }
16}

PHP Solution

1
2php
3function numPairsDivisibleBy60($time) {
4    $remainders = array_fill(0, 60, 0);
5    $count = 0;
6
7    foreach($time as $t) {
8        $remainder = $t % 60;
9        $count += $remainders[(60 - $remainder) % 60];
10        $remainders[$remainder]++;
11    }
12
13    return $count;
14}

Kotlin Solution

1
2kotlin
3class Solution {
4    fun numPairsDivisibleBy60(time: IntArray): Int {
5        val remainders = IntArray(60)
6        var count = 0
7
8        for(t in time) {
9            val remainder = t % 60
10            count += remainders[(60 - remainder) % 60]
11            remainders[remainder]++
12        }
13
14        return count
15    }
16}

In all of these solutions, each song duration is iterated over and its remainder with 60 is calculated. This remainder is used as an index to count the number of song durations having this remainder. Then, for the current song duration, its complement (another song duration that if added to the current song will make the sum divisible by 60) is looked up in the remainder counts array, and added to the running pairs count. Finally, the count of the current song duration's remainder is incremented. This process is repeated for all song durations, giving us the total count of valid song duration pairs.