Count Song Pairs Summing to a Whole Minute

Reported in interviews at Citadel

Problem statement

You are given a list songs of song lengths in seconds. Count the number of unordered pairs of songs whose combined length is a whole number of minutes -- that is, divisible by 60.

Complete:

def numPairsDivisibleBy60(songs: list[int]) -> int:

Constraints:

  • $1 \le \text{len(songs)} \le 6 \times 10^4$, each length a positive integer.

Examples:

  • songs = [30, 20, 150, 100, 40] -> the qualifying pairs sum to 60, 120, and 180 seconds, so the answer is 3.
  • songs = [60, 60, 60] -> every pair sums to 120; there are $\binom{3}{2} = 3$ pairs, so the answer is 3.
  • songs = [10, 50, 90, 30] -> 10 + 50 = 60 and 90 + 30 = 120, so the answer is 2.
Show hint

Which property of each length, rather than the length itself, decides whether two songs combine into whole minutes?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems