# Pairs of Songs With Total Durations Divisible by 60

Published: Sep 21, 2022

Medium Hash Table Counting Array

## Introduction

Basically, the problem asks how many combinations of two are there. In this case, we care about only modulo 60 of each value. Using a hash table to count modulo 60 values is a key to solve this problem.

## Problem Description

You are given a list of songs where the i-th song has a duration of `time[i]` seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices `i, j` such that `i < j` with `(time[i] + time[j]) % 60 == 0`.

Constraints:

• `1 <= time.length <= 6 * 10**4`
• `1 <= time[i] <= 500`

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

## Examples

``````Example 1
Input: time = [30,20,150,100,40]
Output: 3
Explanation: 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
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
``````

## Analysis

The first step is to count modulo 60 values. If modulo 60 is 0 or 30, within that value, two pairs can be created. So, n * (n - 1) / 2 is the number of combinations. If modulo 60 and 60 - modulo 60 are there, for example, 20 and 40, combinations are number of 20 times number of 40. To avoid the pair doubly, up to 30 condition is added.

## Solution

``````class PairOfSongsWithTotalDurationsDivisibleBy60:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
counter = collections.Counter([t % 60 for t in time])
result = 0
for k, v in counter.items():
if k == 0 or k == 30:
result += (v * (v - 1) // 2)
elif k < 30 and 60 - k in counter:
result += (v * counter[60 - k])
return result
``````

## Complexities

• Time: `O(m + n)` – m: length of given array, n: distinct values of x % 60
• Space: `O(n)`