Skip to main content
Talentd

Pairs of Songs With Total Durations Divisible by 60 - Solution & Explanation

MediumArrayHash TableCounting20 min readAsked at: Amazon, Goldman Sachs, Oracle +4
Practice this problem

Problem Statement

You are given a list of songs where the ith 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

Example 2:

Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

 

Constraints:

  • 1 <= time.length <= 6 * 104
  • 1 <= time[i] <= 500

Approach Overview

Problem Overview: You receive an integer array time where each value represents the duration of a song in seconds. The goal is to count how many pairs of songs have a total duration divisible by 60. Two songs form a valid pair if (time[i] + time[j]) % 60 == 0 and i < j.

Approach 1: Brute Force Pair Check (O(n2) time, O(1) space)

The straightforward method checks every possible pair of songs. Use two nested loops: the outer loop picks the first song and the inner loop scans the remaining songs. For each pair, compute (time[i] + time[j]) % 60 and increment a counter when the result equals zero. This approach requires no extra data structures and is easy to implement, but the quadratic time complexity becomes slow when the input size grows. It mainly helps verify correctness before optimizing.

Approach 2: Complementary Remainders with Hash Counting (O(n) time, O(60) space)

The key observation is that only the remainder of each duration modulo 60 matters. If a song has remainder r, it needs another song with remainder (60 - r) % 60 to make the total divisible by 60. Maintain a frequency array or hash map that counts how many songs have each remainder from 0 to 59. As you iterate through the array, compute the current remainder and immediately add the number of previously seen complementary remainders to the answer. Then update the frequency of the current remainder.

This works because every valid pair is discovered exactly once during the single pass. Special handling is naturally covered: remainder 0 pairs with 0, and remainder 30 pairs with 30. The algorithm processes each element once and performs constant‑time lookups, producing an efficient linear solution. The idea is a classic counting trick commonly used in array and hash table problems, especially when solving modular pairing tasks using counting techniques.

Recommended for interviews: Interviewers expect the complementary remainder counting approach. It shows that you recognize modular arithmetic patterns and can convert a pair problem into a frequency lookup. Mentioning the brute force method first demonstrates baseline reasoning, but implementing the O(n) remainder counting solution demonstrates stronger algorithmic insight.

Approach 1: Using Complementary Remainders

This approach uses the idea of complementary remainders. If the sum of the remainders of two numbers when divided by 60 equals 60, then their sum is divisible by 60. For example, if the remainder of a number A is 10, you would need a number B whose remainder is 50 to ensure their sum is divisible by 60 (since 10 + 50 = 60).

We can leverage this by keeping a count of all remainders encountered so far and for each number, check for its complement remainder that, when added, will result in a number divisible by 60.

The C solution uses an array 'remainder' to store counts of remainders of each number in the input divided by 60. For each element, it checks how many elements with a complementary remainder have been seen so far and adds that count to the total.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of songs.
Space Complexity: O(1), since we use a fixed-size array of size 60.

Try this approach in the editor →

Approach 2: Brute Force Approach

In this approach, we use a brute force double loop to compare each pair of songs. For each song, pair it with every other song that comes after it and check if their total duration is divisible by 60. This is a straightforward method but inefficient for large inputs.

Although simple, this method is not optimal for large datasets but can work if constraints are smaller.

The brute force C solution uses nested loops to compute every possible pair of songs and checks if their combined duration is divisible by 60. This results in a simple, albeit inefficient solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^2), iterating over every possible pair.
Space Complexity: O(1), with no additional space used apart from the input array.

Try this approach in the editor →

Approach 3: Math + Counting

If the sum of a pair (a, b) is divisible by 60, i.e., (a + b) bmod 60 = 0, then (a bmod 60 + b bmod 60) bmod 60 = 0. Let x = a bmod 60 and y = b bmod 60, then (x + y) bmod 60 = 0, which means y = (60 - x) bmod 60.

Therefore, we can iterate over the song list and use an array cnt of length 60 to record the number of occurrences of each remainder x. For the current x, if there exists a remainder y = (60 - x) bmod 60 in array cnt, we add cnt[y] to the answer. Then we increment the count of x in array cnt by 1. We continue iterating until the entire song list has been traversed.

After the iteration, we get the number of song pairs that satisfy the condition.

The time complexity is O(n) and the space complexity is O(C), where n is the length of the song list and C is the number of possible remainders, here C = 60.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Complementary Remainders

Time Complexity: O(N), where N is the number of songs.
Space Complexity: O(1), since we use a fixed-size array of size 60.

Brute Force Approach

Time Complexity: O(N^2), iterating over every possible pair.
Space Complexity: O(1), with no additional space used apart from the input array.

Math + Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n^2)O(1)Useful for small inputs or to validate logic before optimizing
Complementary Remainder Counting (Hash/Array)O(n)O(60)Best general solution; single pass with constant-time remainder lookups

Video Solution

Pairs of songs with total durations divisible by 60 | Leetcode #1010 • Techdose • 27,437 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Pairs of Songs With Total Durations Divisible by 60 easy or hard?
The problem is rated Medium. The challenge is recognizing that only remainders modulo 60 matter and transforming the pair search into a counting problem, which reduces the complexity from O(n^2) to O(n).
How to solve Pairs of Songs With Total Durations Divisible by 60 in O(n)?
Compute the remainder of each song duration modulo 60. For each remainder r, the required partner remainder is (60 - r) % 60. Maintain a frequency array of previously seen remainders and add the count of the complementary remainder before updating the current remainder count.
Pairs of Songs With Total Durations Divisible by 60 Python or Java solution?
Python and Java solutions typically implement the O(n) remainder counting method. Both languages maintain an array of size 60 to track remainder frequencies and update the pair count during a single pass through the input array.
What is the best approach for Pairs of Songs With Total Durations Divisible by 60?
The optimal approach uses complementary remainders with a hash map or fixed array of size 60. For each song duration, compute duration % 60 and look for the complement (60 − remainder) % 60 that has already appeared. This allows counting valid pairs in O(n) time with O(60) extra space.
What data structure is used in Pairs of Songs With Total Durations Divisible by 60?
The optimal solution uses a hash table or a fixed counting array of size 60. The structure stores how many songs have each remainder when divided by 60, allowing constant‑time lookup for complementary remainders.
What is the time complexity of Pairs of Songs With Total Durations Divisible by 60?
The brute force solution runs in O(n^2) time because it checks every pair of songs. The optimized approach using remainder counting runs in O(n) time since each element is processed once and hash/array lookups are constant time.
Is Pairs of Songs With Total Durations Divisible by 60 asked at Google, Amazon, or Meta?
This problem appears in interview preparation sets for companies such as Amazon and Google because it tests hash table usage, modular arithmetic, and counting patterns. It is commonly used to evaluate whether candidates can reduce pair problems from O(n^2) to O(n).

Ready to solve this problem?

Practice Pairs of Songs With Total Durations Divisible by 60 with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Pairs That Form a Complete Day II

Next

Destroy Sequential Targets