MediumArrayHash TableCountingUpdated Sep 2026

1010. Pairs of Songs With Total Durations Divisible by 60

Asked at Atlassian

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array time, where time[i] is the length in seconds of the i-th song. Count how many pairs of songs (i, j) have i < j and a total length that is a multiple of 60.

A pair is just two different songs, and the order does not matter: the pair (i, j) with i < j is counted once. Two songs with the same length are still different songs, so they can form a pair.

Return the number of such pairs. The array can be large, so you need something faster than checking every pair by hand.

Which pairs sum to a multiple of 60

time3020150100400123430+150=180, 20+100=120 and 20+40=60 are all divisibleby 60.
Only three pairs in this list add up to a multiple of 60, so the answer is 3.

Constraints

  • ●1 <= time.length <= 6 * 10^4
  • ●1 <= time[i] <= 500

Examples

Example 1
Inputtime = [30,20,150,100,40]
Output3
WhyThe valid pairs are (30, 150) = 180, (20, 100) = 120, and (20, 40) = 60. Each total is a multiple of 60, and no other pair works.
Example 2
Inputtime = [60,60,60]
Output3
WhyEvery pair sums to 120, which is divisible by 60. With 3 songs there are 3 ways to choose 2 of them.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Compute remainder of each duration when divided by 60

2

Use hash map to count occurrences of each remainder

3

For remainder r, find complement (60 - r) % 60 in the map

4

Handle special case where remainder is 0 (pairs with other 0s)

5

Count pairs incrementally while iterating for O(n) solution

Optimal Approach

Use modular arithmetic to track remainders when dividing durations by 60. Maintain a count of each remainder seen so far. For each new duration with remainder r, the complement is (60 - r) % 60. Add the count of that complement to the result. Increment the count of the current remainder. This yields O(n) time with O(1) space since remainders range from 0 to 59.

Count remainders, not pairs

time30201501004001234r=30At 150 the remainder is 30, and one earlier song (30)has remainder 30, so we add 1.r = t % 60need = (60 - r) % 60answer += count[need]count[r] += 1
For each song we look up how many earlier songs have the remainder that completes it to 60.
ComplexityTime O(n)Space O(1)We scan the array once, and the remainder counter always has exactly 60 slots, so the extra space does not grow with n.

What Trips People Up in Real Interviews

1

Clarify that remainder 0 pairs with remainder 0, not 60

2

Explain why (60 - r) % 60 handles both r=0 and r=30 cases

3

Discuss the O(n) time and O(1) space solution using counting

4

Mention edge case: all songs exactly 60 minutes long

5

Consider how to extend to divisibility by arbitrary number

Solution Code

O(n) time
def numPairsDivisibleBy60(time):
    count = [0] * 60
    result = 0
    for t in time:
        r = t % 60
        complement = (60 - r) % 60
        result += count[complement]
        count[r] += 1
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Pairs of Songs With Total Durations Divisible by 60 problem?

Given a list of song durations, find how many pairs of songs have total duration divisible by 60. Each pair (i, j) where i < j counts once. The solution must handle large inputs efficiently using modular arithmetic.

How do you solve Pairs of Songs With Total Durations Divisible by 60?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Pairs of Songs With Total Durations Divisible by 60?

Pairs of Songs With Total Durations Divisible by 60 is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Pairs of Songs With Total Durations Divisible by 60?
  • Clarify that remainder 0 pairs with remainder 0, not 60
  • Explain why (60 - r) % 60 handles both r=0 and r=30 cases
  • Discuss the O(n) time and O(1) space solution using counting
  • Mention edge case: all songs exactly 60 minutes long
  • Consider how to extend to divisibility by arbitrary number