Pairs of Songs With Total Durations Divisible by 60 solution and explanation
Google
9 more videos on this problem
Pairs of songs with total durations divisible by 60 | Leetcode #1010Techdose · 19:55 · 27K views
LeetCode 1010. Pairs of Songs with Total Durations Divisible by 60 [Coding Question Explained]Shiran Afergan · 10:04 · 9K views
Pairs of Songs With Total Durations Divisible by 60 | Live Coding with Explanation | Leetcode #1010Algorithms Made Easy · 3:54 · 7K views
PAIRS OF SONGS DIVISIBLE BY 60 | LEETCODE # 1010 | PYTHON SOLUTIONCracking FAANG · 15:36 · 5K views
Leetcode 1010. Pairs of Songs With Total Durations Divisible by 60 (Python) FULL EXPLANATIONCooper Codes · 13:31 · 2K views
Pairs of Songs With Total Durations Divisible by 60 | LeetCode 1010 | C++Knowledge Center · 16:36 · 2K views
Amazon Coding Interview Question | Leetcode 1010 | Pairs of Songs With Total Durations Divisible 60WorkWithGoogler · 11:13 · 2K views
Pairs of Songs With Total Durations Divisible by 60 | Leetcode1010 | Live coding session 🔥🔥🔥 | O(n)Coding Decoded · 10:41 · 1K views
1010. Pairs of Songs with Total Durations Divisible by 60 (LeetCode)hakunamatasq · 4:39 · 752 views
Pair of Songs with Total duration by 60 | Leetcode 1010 | |Java Array | Leetcode mastery | Manish |Manish Harit · 12:57 · 434 views
The problem
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 * 1041 <= 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.
def numPairsDivisibleBy60(time):
remainder = [0] * 60
count = 0
for t in time:
rem = t % 60
complement = (60 - rem) % 60
count += remainder[complement]
remainder[rem] += 1
return count
if __name__ == "__main__":
time = [30, 20, 150, 100, 40]
print(numPairsDivisibleBy60(time))import java.util.*;
public class SongPairs {
public static int numPairsDivisibleBy60(int[] time) {
int[] remainder = new int[60];
int count = 0;
for (int t : time) {
int rem = t % 60;
int complement = (60 - rem) % 60;
count += remainder[complement];
remainder[rem]++;
}
return count;
}
public static void main(String[] args) {
int[] time = {30, 20, 150, 100, 40};
System.out.println(numPairsDivisibleBy60(time));
}
}#include <vector>
#include <iostream>
using namespace std;
int numPairsDivisibleBy60(vector<int>& time) {
vector<int> remainder(60, 0);
int count = 0;
for (int t : time) {
int rem = t % 60;
int complement = (60 - rem) % 60;
count += remainder[complement];
remainder[rem]++;
}
return count;
}
int main() {
vector<int> time = {30, 20, 150, 100, 40};
cout << numPairsDivisibleBy60(time) << endl;
return 0;
}function numPairsDivisibleBy60(time) {
let remainder = new Array(60).fill(0);
let count = 0;
for (let t of time) {
let rem = t % 60;
let complement = (60 - rem) % 60;
count += remainder[complement];
remainder[rem]++;
}
return count;
}
let time = [30, 20, 150, 100, 40];
console.log(numPairsDivisibleBy60(time));#include <stdio.h>
int numPairsDivisibleBy60(int* time, int timeSize) {
int remainder[60] = {0};
int count = 0;
for (int i = 0; i < timeSize; i++) {
int rem = time[i] % 60;
int complement = (60 - rem) % 60;
count += remainder[complement];
remainder[rem]++;
}
return count;
}
int main() {
int time[] = {30, 20, 150, 100, 40};
int size = sizeof(time) / sizeof(time[0]);
printf("%d\n", numPairsDivisibleBy60(time, size));
return 0;
}using System;
public class SongPairs {
public static int NumPairsDivisibleBy60(int[] time) {
int[] remainder = new int[60];
int count = 0;
foreach (int t in time) {
int rem = t % 60;
int complement = (60 - rem) % 60;
count += remainder[complement];
remainder[rem]++;
}
return count;
}
public static void Main() {
int[] time = new int[] {30, 20, 150, 100, 40};
Console.WriteLine(NumPairsDivisibleBy60(time));
}
}The Python implementation uses a list to count remainders and checks for the complementary remainder during each iteration to find the required number of pairs.
Time Complexity: O(N), with N being the number of songs.
Space Complexity: O(1), using a fixed-size list.
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.
def numPairsDivisibleBy60(time):
count = 0
for i in range(len(time) - 1):
for j in range(i + 1, len(time)):
if (time[i] + time[j]) % 60 == 0:
count += 1
return count
if __name__ == "__main__":
time = [30, 20, 150, 100, 40]
print(numPairsDivisibleBy60(time))public class SongPairsBruteForce {
public static int numPairsDivisibleBy60(int[] time) {
int count = 0;
for (int i = 0; i < time.length - 1; i++) {
for (int j = i + 1; j < time.length; j++) {
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] time = {30, 20, 150, 100, 40};
System.out.println(numPairsDivisibleBy60(time));
}
}#include <vector>
#include <iostream>
using namespace std;
int numPairsDivisibleBy60(vector<int>& time) {
int count = 0;
for (int i = 0; i < time.size() - 1; i++) {
for (int j = i + 1; j < time.size(); j++) {
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
int main() {
vector<int> time = {30, 20, 150, 100, 40};
cout << numPairsDivisibleBy60(time) << endl;
return 0;
}function numPairsDivisibleBy60(time) {
let count = 0;
for (let i = 0; i < time.length - 1; i++) {
for (let j = i + 1; j < time.length; j++) {
if ((time[i] + time[j]) % 60 === 0) {
count++;
}
}
}
return count;
}
let time = [30, 20, 150, 100, 40];
console.log(numPairsDivisibleBy60(time));#include <stdio.h>
int numPairsDivisibleBy60(int* time, int timeSize) {
int count = 0;
for (int i = 0; i < timeSize - 1; i++) {
for (int j = i + 1; j < timeSize; j++) {
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
int main() {
int time[] = {30, 20, 150, 100, 40};
int size = sizeof(time) / sizeof(time[0]);
printf("%d\n", numPairsDivisibleBy60(time, size));
return 0;
}using System;
public class SongPairsBruteForce {
public static int NumPairsDivisibleBy60(int[] time) {
int count = 0;
for (int i = 0; i < time.Length - 1; i++) {
for (int j = i + 1; j < time.Length; j++) {
if ((time[i] + time[j]) % 60 == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] time = new int[] {30, 20, 150, 100, 40};
Console.WriteLine(NumPairsDivisibleBy60(time));
}
}The Python brute force approach follows the dual loop structure to test each possible song pair, increasing the count of valid pairs whose total duration is divisible by 60.
Time Complexity: O(N^2) due to checking each pair.
Space Complexity: O(1), beyond the input list.
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.
function numPairsDivisibleBy60(time: number[]): number {
const cnt: number[] = new Array(60).fill(0);
let ans: number = 0;
for (let x of time) {
x %= 60;
const y = (60 - x) % 60;
ans += cnt[y];
++cnt[x];
}
return ans;
}func numPairsDivisibleBy60(time []int) (ans int) {
cnt := [60]int{}
for _, x := range time {
x %= 60
y := (60 - x) % 60
ans += cnt[y]
cnt[x]++
}
return
}impl Solution {
pub fn num_pairs_divisible_by60(time: Vec<i32>) -> i32 {
let mut cnt = [0i32; 60];
let mut ans: i32 = 0;
for mut x in time {
x %= 60;
let y = (60 - x) % 60;
ans += cnt[y as usize];
cnt[x as usize] += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Complementary Remainders | Time Complexity: O(N), with N being the number of songs. |
| Brute Force Approach | Time Complexity: O(N^2) due to checking each pair. |
| Math + Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(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 |
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).