Pairs of Songs With Total Durations Divisible by 60

Pairs of Songs With Total Durations Divisible by 60 - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: time = [30,20,150,100,40]

› Output: 3

💡 Note: Three pairs sum to multiples of 60: (30,150)=180, (20,40)=60, (100,40)=140. Wait, let me recalculate: (30,150)=180≡0, (20,40)=60≡0, (30,30) from positions would be invalid since we need i

Example 2 — Multiple Zeros

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

› Output: 3

💡 Note: All songs are 60 seconds (remainder 0). Every pair sums to 120≡0 (mod 60). Pairs: (0,1), (0,2), (1,2) = 3 pairs total.

Example 3 — No Valid Pairs

$ Input: time = [10,50,90,30]

› Output: 1

💡 Note: Remainders: 10, 50, 30, 30. Only 10+50=60≡0 (mod 60) forms a valid pair.

Constraints

1 ≤ time.length ≤ 6 × 10⁴
1 ≤ time[i] ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input

Array of song durations in seconds

Process

Find pairs where sum is divisible by 60

Output

Count of valid pairs

Key Takeaway

🎯 Key Insight: Use modular arithmetic - remainders that sum to 60 (or both 0/30) form valid pairs

Asked in

a Amazon 15 f Facebook 8

The key insight is using modular arithmetic: two numbers sum to a multiple of 60 if their remainders sum to 60. Best approach is frequency counting with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count - Remainder Grouping	O(n)	O(1)	Count remainders when divided by 60, then count complementary pairs
Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair of songs to see if their sum is divisible by 60

Frequency Count - Remainder Grouping — Algorithm Steps

Calculate remainder for each song duration: time[i] % 60
Count frequency of each remainder (0 to 59)
For remainder 0: pairs = count[0] * (count[0]-1) / 2
For remainder 30: pairs = count[30] * (count[30]-1) / 2
For remainders 1-29: pairs = count[i] * count[60-i]

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Remainders

Find remainder when each duration is divided by 60

Count Frequencies

Count how many songs have each remainder

Pair Complements

Match remainders that sum to 60

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* time, int n) {
    int remainderCount[60] = {0};
    
    // Count frequency of each remainder
    for (int i = 0; i < n; i++) {
        remainderCount[time[i] % 60]++;
    }
    
    int count = 0;
    
    // Special case for remainder 0 (pairs within same group)
    count += remainderCount[0] * (remainderCount[0] - 1) / 2;
    
    // Special case for remainder 30 (pairs within same group)
    count += remainderCount[30] * (remainderCount[30] - 1) / 2;
    
    // For remainders 1-29, pair with complement (60-remainder)
    for (int i = 1; i < 30; i++) {
        count += remainderCount[i] * remainderCount[60 - i];
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int time[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        time[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    int result = solution(time, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to count remainders, then O(1) calculation for pairs

✓ Linear Growth

Space Complexity

O(1)

Fixed array of size 60 to store remainder counts

✓ Linear Space

60.4K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count - Remainder Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler