Problem Breakdown
We need to count the number of index pairs (i, j) such that i < j and (time[i] + time[j]) % 60 == 0.
The core challenge is doing this efficiently given up to , which rules out an brute-force approach.
Key observations:
- Modular Arithmetic:
(a + b) % k == 0impliesb % k = (k - a % k) % k. We only care about the remainder of each song duration when divided by 60. - Frequency Counting: Instead of checking every future element for every current element, we can maintain how many times each remainder has appeared so far.
Intuition
A brute-force solution checks all pairs which takes . To optimize to :
- We iterate through the list once.
- For each song
t, we calculate its remainderr = t % 60. - The required complement remainder is
(60 - r) % 60. - If a previous song had this complement remainder, it forms valid pairs with the current song. We add the count of such songs to our total.
- Then we increment the frequency map for
rso future songs can pair with it.
This transforms the problem into counting compatible remainders encountered previously in a single pass. The space complexity is effectively constant because there are only 60 possible remainder values (0-59).
Approach
- Initialize a counter
total_pairs = 0. - Use a hash map (
remainder_counts) to store the frequency of each remainder encountered so far. - Iterate through each duration
tintime:- Compute
rem = t % 60. - Calculate target complement:
target = (60 - rem) % 60.- Note: If
rem == 0,(60-0)%60results in0, correctly pairing multiples of 60 with each other.
- Note: If
- Add the count of songs seen so far that have remainder equal to
targetintototal_pairs. - Increment the frequency map for the current song’s remainder (
rem).
- Compute
- Return
total_pairs.
Complexity Analysis
- Time Complexity: , where is the number of songs in the input list. We iterate through the array exactly once with constant-time dictionary operations (hashing).
- Space Complexity: or effectively . The hash map stores counts for remainders 0-59. Since there are only 60 possible distinct values, the space usage is bounded by a small constant regardless of input size ().
Solution
from typing import List
from collections import defaultdict
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
# Frequency map to store count of remainders encountered so far.
# Using defaultdict(int) simplifies incrementing counts without checking existence first.
remainder_counts = defaultdict(int)
total_pairs = 0
for t in time:
rem = t % 60
# Calculate the complement needed to sum up to a multiple of 60.
# If rem is 0, target becomes (60-0)%60 -> 0.
# This correctly handles cases where we need another multiple of 60.
target = (60 - rem) % 60
# Add existing compatible pairs found before this song to the total count
ans += remainder_counts[target]
# Record current remainder for future songs to pair with
counts[rem] += 1
return ans
# Alternative concise implementation using standard dict if defaultdict is not preferred:
class Solution2:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
remainder_counts = {}
total_pairs = 0
for t in time:
rem = t % 60
target = (60 - rem) % 60
if target in remainder_counts:
total_pairs += remainder_counts[target]
# Update frequency map using .get() to handle initialization implicitly or explicit check
remainder_counts[rem] = remainder_counts.get(rem, 0) + 1
return total_pairs
# Final optimized version for submission (using defaultdict is cleaner):
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
counts = defaultdict(int)
ans = 0
for t in time:
rem = t % 60
target = (60 - rem) % 60
# Add existing compatible pairs found before this song
ans += counts[target]
# Record current remainder for future songs to pair with
counts[rem] += 1
return ans
Edge Cases Handled
- **Remainder Zero