Song Pairs Filling Whole Minutes
Problem
You are given the lengths of songs in seconds. Count the pairs of songs, at positions i < j, whose total length is a whole number of minutes, meaning the sum of the two lengths is divisible by 60.
Examples
Input: times = [30, 20, 150, 100, 40]
Output: 3
Why: 30 + 150, 20 + 100 and 20 + 40 are 180, 120 and 60 secondsInput: times = [60, 60, 60]
Output: 3
Why: every pair of the three songs adds up to 120 secondsInput: times = [10, 20]
Output: 0
Why: edge case, 30 seconds is not a whole minuteHints
0 / 3
Checking every pair is O(n²). Only one property of each length matters for divisibility by 60. Which one?
(x + y) % 60 == 0 exactly when x % 60 and y % 60 add up to 0 or 60. A song with remainder r needs a partner with remainder (60 - r) % 60.
Walk the list once with a count of every remainder seen so far. For each song, add the count of the remainder it needs, then record its own remainder.
Solution
Divisibility by 60 depends only on remainders: (x + y) % 60 equals (x % 60 + y % 60) % 60, so there are just 60 kinds of song. A song with remainder r completes a whole minute with any earlier song whose remainder is (60 - r) % 60; the outer % 60 makes a remainder of 0 pair with 0 rather than with a nonexistent 60, which is also what covers 30 pairing with 30. Counting partners among the songs already seen, before adding the current one, counts each pair exactly once and never pairs a song with itself. Time is O(n) and space is O(1), since the table never holds more than 60 entries.
def whole_minute_pairs(times):
seen = [0] * 60 # how many earlier songs have each remainder
pairs = 0
for t in times:
r = t % 60
pairs += seen[(60 - r) % 60] # earlier songs that complete a minute
seen[r] += 1
return pairs
print(whole_minute_pairs([30, 20, 150, 100, 40])) # -> 3
print(whole_minute_pairs([60, 60, 60])) # -> 3
print(whole_minute_pairs([10, 20])) # -> 0Stuck on the idea rather than the code? Modular Arithmetic covers it.