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: 2

💡 Note: Pairs that sum to multiples of 60: (10,50)=60 and (90,30)=120, so 2 pairs total.

Constraints

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

Visualization

Tap to expand

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

✓ Brute Force - Check All Pairs

⏱️ Time: O(n²) Space: O(1)

Iterate through all pairs (i,j) where i < j and count how many have (time[i] + time[j]) % 60 == 0. This is straightforward but inefficient for large inputs.

Frequency Count - Remainder Grouping

⏱️ Time: O(n) Space: O(1)

Instead of checking all pairs, we group songs by their remainder when divided by 60. Two songs form a valid pair if their remainders sum to 60 (or both are 0 or 30).

Brute Force - Check All Pairs — Algorithm Steps

Outer loop: iterate i from 0 to n-2
Inner loop: iterate j from i+1 to n-1
Check if (time[i] + time[j]) % 60 == 0
If yes, increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Pairs

Compare every song with every other song

Test Divisibility

Sum durations and check if divisible by 60

Count Valid

Count pairs that sum to multiples of 60

Code -

solution.c — C

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

int solution(int* time, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((time[i] + time[j]) % 60 == 0) {
                count++;
            }
        }
    }
    return count;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

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²)

Nested loops check all n*(n-1)/2 pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only using counter variable

✓ 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

Pairs of Songs With Total Durations Divisible by 60 - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler