Leetcode 1010: Pairs of Songs With Total Durations Divisible by 60

Input: The input consists of an array of integers where each integer represents the duration of a song in seconds.

Example: time = [10, 50, 120, 80, 40]

Constraints:

• 1 <= time.length <= 6 * 10^4

• 1 <= time[i] <= 500

Output: The output should be the total number of valid pairs where the sum of the song durations is divisible by 60.

Example: Output: 2

Constraints:

• The result should be an integer representing the number of valid pairs.

Goal: The goal is to efficiently count the pairs of songs whose combined durations are divisible by 60.

Steps:

• For each song, find the remainder when the song's duration is divided by 60.

• Count how many other songs, when paired with the current song, have a remainder that completes the sum to be divisible by 60.

• Maintain a count of song durations modulo 60 to avoid recalculating the remainder each time.

Goal: Ensure that the solution can handle large inputs efficiently and correctly.

Steps:

• The input list can contain up to 6 * 10^4 song durations, so the solution should have an optimized time complexity.

Assumptions:

• Each song duration is unique, and all are between 1 and 500 seconds.

• Input: Input: time = [10, 50, 120, 80, 40]

• Explanation: In this case, two pairs of songs have durations that add up to a multiple of 60: (time[0] = 10, time[1] = 50) and (time[2] = 120, time[4] = 40). These pairs add up to 60 and 160, respectively, both of which are divisible by 60.

• Input: Input: time = [60, 60, 60]

• Explanation: For this input, all three pairs (time[0] = 60, time[1] = 60), (time[0] = 60, time[2] = 60), and (time[1] = 60, time[2] = 60) add up to 120, which is divisible by 60. Therefore, the output is 3.

Approach: The strategy involves using modular arithmetic to find complementary pairs of song durations that sum to a multiple of 60. We use a hash map or array to track the number of song durations with specific remainders when divided by 60.

Observations:

• We need to track the remainder of each song's duration modulo 60 to find pairs that add up to multiples of 60.

• A hash map or a fixed-size array can be used to efficiently count how many song durations correspond to each remainder modulo 60.

Steps:

• 1. Initialize an array of size 60 to store the count of each remainder (0 to 59).

• 2. For each song, compute its remainder when divided by 60 and find how many previous songs have the complementary remainder that makes the sum divisible by 60.

• 3. Update the remainder count for the current song's duration.

Empty Inputs:

• The input will never be empty as per the problem constraints.

Large Inputs:

• The solution should efficiently handle large inputs (up to 60,000 elements).

Special Values:

• If all songs have durations that are multiples of 60, every pair will be valid.

Constraints:

• The input array size and the song duration values should be within the specified constraints.

int numPairsDivisibleBy60(vector<int>& time) {
    vector<int> c(60, 0);
    int res = 0;
    for(int t: time) {
        res += c[(600 - t)%60];
        c[t%60] += 1;
    }
    return res;
}

1 : Function Declaration

int numPairsDivisibleBy60(vector<int>& time) {

Declares the function `numPairsDivisibleBy60` which takes a vector of integers `time` representing the time intervals, and returns the number of valid pairs whose sum is divisible by 60.

2 : Array Initialization

    vector<int> c(60, 0);

Initializes a vector `c` of size 60 to count the occurrences of remainders when each time value is divided by 60.

3 : Variable Initialization

    int res = 0;

Initializes the result variable `res` to 0, which will store the number of valid pairs found.

4 : Loop Start

    for(int t: time) {

Starts a loop that iterates through each element `t` in the input `time` vector.

5 : Pair Calculation

        res += c[(600 - t)%60];

For each time value `t`, adds to `res` the count of previously seen time values that form a valid pair with `t` (i.e., their sum is divisible by 60). This is done using the frequency array `c`.

6 : Frequency Update

        c[t%60] += 1;

Increments the count of occurrences for the current remainder `t%60` in the frequency array `c`.

7 : Return Statement

    return res;

Returns the total number of valid pairs found.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we iterate through the list of songs once, and each operation (remainder calculation and count update) takes constant time.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we use a fixed-size array of length 60 to store remainder counts.

Leetcode 1010: Pairs of Songs With Total Durations Divisible by 60

Explore →