https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60

If you are familiar with modular arithmetic, this problem will be very easy for you. So, we need to find number of pairs of songs, such that total duration in each pair is divisible by 60: there can be several cases how it is possible. Imagine we have 2 songs a and b, then: [1]. a and b have reminders 0. [2]. a has reminder 1 and b has reminder 59. [3]. a has reminder 2 and b has reminder 58.

[59]. a has reminder 58 and b has reminder 2. [60] a has reminder 59 and b has reminder 1.

So, what we need to do now: for each reminder calculate how many number we have with this reminder and then evaluate sum of products: a1*a59 + a2*a58 + ..., where a1 is number of numbers with reminder 1 and so on. Also we need to be careful with reminders 0 and 30: for them we need to choose number of combinations.

Complexity: time complexity is O(n), space complexity is O(60) = O(1).

class Solution:
    def numPairsDivisibleBy60(self, time):
        d, T = Counter(), 60
        for t in time: d[t%T] += 1
        ans = sum(d.get(i,0)*d.get(T-i,0) for i in range(1, T//2))
        q1, q2 = d.get(0,0), d.get(T//2, 0)
        return ans + q1*(q1-1)//2 + q2*(q2-1)//2

If you like the solution, you can upvote it on leetcode discussion section: Problem 1010