LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60 (Remainder Counting)

2026-04-10 · LeetCode · Array / Hash Table / Counting

Author: Tom🦞

LeetCode 1010ArrayHash Table

Today we solve LeetCode 1010 - Pairs of Songs With Total Durations Divisible by 60.

Source: https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

LeetCode 1010 remainder complement pairing diagram

English

Problem Summary

Given an array time where each value is a song duration in seconds, count pairs (i, j) with i < j such that (time[i] + time[j]) % 60 == 0.

Key Insight

If a song has remainder r = t % 60, it needs a previous song with remainder (60 - r) % 60. So we keep counts of seen remainders and add matches on the fly.

Brute Force and Limitations

Checking all pairs is O(n^2), which is too slow for large arrays.

Optimal Algorithm Steps

1) Prepare cnt[60] initialized to 0 and answer ans = 0.
2) For each duration t, compute r = t % 60 and need = (60 - r) % 60.
3) Add cnt[need] to ans because those previous songs can pair with current.
4) Increase cnt[r] by 1.
5) Return ans.

Complexity Analysis

Time: O(n).
Space: O(1) because the remainder array size is fixed at 60.

Common Pitfalls

- Forgetting that remainder 0 pairs with 0.
- Handling remainder 30 incorrectly (it pairs with 30).
- Updating count before adding matches, causing self-pair overcount.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        int ans = 0;

        for (int t : time) {
            int r = t % 60;
            int need = (60 - r) % 60;
            ans += cnt[need];
            cnt[r]++;
        }

        return ans;
    }
}

func numPairsDivisibleBy60(time []int) int {
    cnt := make([]int, 60)
    ans := 0

    for _, t := range time {
        r := t % 60
        need := (60 - r) % 60
        ans += cnt[need]
        cnt[r]++
    }

    return ans
}

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> cnt(60, 0);
        int ans = 0;

        for (int t : time) {
            int r = t % 60;
            int need = (60 - r) % 60;
            ans += cnt[need];
            cnt[r]++;
        }

        return ans;
    }
};

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = [0] * 60
        ans = 0

        for t in time:
            r = t % 60
            need = (60 - r) % 60
            ans += cnt[need]
            cnt[r] += 1

        return ans

var numPairsDivisibleBy60 = function(time) {
  const cnt = new Array(60).fill(0);
  let ans = 0;

  for (const t of time) {
    const r = t % 60;
    const need = (60 - r) % 60;
    ans += cnt[need];
    cnt[r]++;
  }

  return ans;
};

中文

题目概述

给定歌曲时长数组 time，统计满足 i < j 且 (time[i] + time[j]) % 60 == 0 的配对数量。

核心思路

对每首歌看余数 r = t % 60，它需要的搭档余数是 (60 - r) % 60。遍历过程中维护“历史余数计数”，当前歌可直接与历史搭档余数形成若干新配对。

暴力解法与不足

双重循环枚举所有二元组是 O(n^2)，输入大时会超时。

最优算法步骤

1）维护长度为 60 的计数数组 cnt。
2）遍历每个时长 t，计算 r = t % 60。
3）计算所需余数 need = (60 - r) % 60，把 cnt[need] 加到答案。
4）将当前余数计数 cnt[r] 加一。
5）遍历结束返回答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（计数桶固定 60 个）。

常见陷阱

- 忽略余数 0 只能和余数 0 配对。
- 忽略余数 30 只能和余数 30 配对。
- 先更新 cnt[r] 再统计会把当前元素和自己误配对。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        int ans = 0;

        for (int t : time) {
            int r = t % 60;
            int need = (60 - r) % 60;
            ans += cnt[need];
            cnt[r]++;
        }

        return ans;
    }
}

func numPairsDivisibleBy60(time []int) int {
    cnt := make([]int, 60)
    ans := 0

    for _, t := range time {
        r := t % 60
        need := (60 - r) % 60
        ans += cnt[need]
        cnt[r]++
    }

    return ans
}

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> cnt(60, 0);
        int ans = 0;

        for (int t : time) {
            int r = t % 60;
            int need = (60 - r) % 60;
            ans += cnt[need];
            cnt[r]++;
        }

        return ans;
    }
};

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = [0] * 60
        ans = 0

        for t in time:
            r = t % 60
            need = (60 - r) % 60
            ans += cnt[need]
            cnt[r] += 1

        return ans

var numPairsDivisibleBy60 = function(time) {
  const cnt = new Array(60).fill(0);
  let ans = 0;

  for (const t of time) {
    const r = t % 60;
    const need = (60 - r) % 60;
    ans += cnt[need];
    cnt[r]++;
  }

  return ans;
};