We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pairs of Songs With Total Durations Divisible by 60

Number: 1055

Difficulty: Medium

Paid? No

Companies: PayPal, TikTok, Goldman Sachs, Oracle, Amazon, BlackRock, J.P. Morgan, Google, Nvidia, Docusign, Salesforce, Atlassian

Problem Description

Given an array of song durations (in seconds), determine the number of pairs of songs (i, j with i < j) such that the sum of their durations is divisible by 60.

Key Insights

  • Each song duration's effect is determined by its remainder when divided by 60.
  • For any given module value r (where 0 ≤ r < 60), the complementary module needed to complete 60 is (60 - r) % 60.
  • Special handling is needed when r is 0 (or 30, since 30 + 30 = 60) to avoid double-counting.
  • A frequency counter for remainders can be efficiently used to count valid pairs in one pass through the list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of songs. Space Complexity: O(60) → O(1), since we only need to keep track of 60 possible remainders.

Solution

We iterate over the list of song durations and calculate the remainder of each duration modulo 60. A frequency array (or hash table) is used to record how many times each remainder has been seen so far. For each song, we look up the frequency of its complementary remainder (i.e., (60 - current_remainder) % 60) already encountered. This frequency indicates how many valid pairs can be formed with the current song. After counting pairs with the current song, we update the frequency of its remainder for future pairings.

Code Solutions

# Python solution for counting pairs of songs whose duration sums are divisible by 60
def numPairsDivisibleBy60(time):
    # Frequency array for remainders 0-59
    remainder_freq = [0] * 60
    pair_count = 0
    
    # Loop over each song duration
    for t in time:
        # Calculate the remainder when dividing by 60
        remainder = t % 60
        # Calculate the complementary remainder needed for the sum to be divisible by 60
        complement = (60 - remainder) % 60
        # Increase pair count by frequency of complement seen so far
        pair_count += remainder_freq[complement]
        # Update the frequency counter for the current remainder
        remainder_freq[remainder] += 1
    
    return pair_count

# Example usage
# print(numPairsDivisibleBy60([30,20,150,100,40]))  # Expected output: 3
← Back to All Questions