Pair of Songs With Total Durations Divisible by 60

January 26, 2024

Problem Statement #

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.

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

Solution Approach #

The solution involves using a hashmap to keep track of the frequencies of song durations modulo 60.

Algorithm Steps #

1. Create a hashmap to store frequencies of song durations modulo 60.
2. Iterate over the list of song durations.
3. For each duration, find the complement duration that makes the sum divisible by 60.
4. Count the number of valid pairs using the hashmap.
5. Update the hashmap with the current song duration.
6. Return the total count of pairs.

Code (Python) #

def numPairsDivisibleBy60(time):
    remainder_map = [0] * 60
    count = 0

    for t in time:
        if t % 60 == 0:  # Check for pairs with both songs having multiples of 60
            count += remainder_map[0]
        else:
            count += remainder_map[60 - t % 60]
        remainder_map[t % 60] += 1

    return count

# Test the function
print(numPairsDivisibleBy60([30, 20, 150, 100, 40]))  # Output: 3

Time Complexity #

O(n), where n is the number of songs. The time array is traversed once.

Space Complexity #

O(1), as the space for the remainder map is constant (60 elements).