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

Description Hints 2 Solution Video 19:55

1010. Pairs of Songs With Total Durations Divisible by 60

Medium53.6% acceptance7 companies

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.

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 * 10⁴
1 <= time[i] <= 500

Asked at 7 companies

PayPal Goldman Sachs Tiktok Oracle Atlassian Amazon

Google

Topics

Hints open one at a time

Hint 1

We only need to consider each song length modulo 60.

Hint 2

We can count the number of songs having same (length % 60), and store that in an array of size 60.

19:55

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution