[leetcode #1010] Pairs of Songs With Total Durations Divisible by 60

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

Idea

두 노래의 재생시간 합이 분 단위인 개수를 계산하는 문제다.

우선 재생시간의 합이 분 단위가 되려면 60으로 나눈 나머지의 합이 0이거나 60이어야 한다. 따라서 처음에 주어진 재생시간을 돌면서 60으로 나눈 나머지의 개수를 센다.

나머지가 0이나 30인 경우를 제외하면 현재 나머지를 i라고 할 때 현재 경우의 수와 나머지가 (60 - i)인 경우의 개수와 곱한 값이 가능한 경우의 수가 된다.

나머지가 0이거나 30인 경우는 n개의 수 중 2개를 뽑는 경우이므로 n * (n - 1) / 2가 경우의 수가 된다.

위 가능한 경우의 수를 모두 합하여 리턴하면 된다.

Time Complexity: O(n)

Solution

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

        for (int duration : time) {
            cnt[duration % 60]++;
        }

        int res = 0;
        for (int i=1; i < 30; i++) {
            res += cnt[i] * cnt[60-i];
        }
        res += cnt[0] * (cnt[0] - 1)  / 2;
        res += cnt[30] * (cnt[30] - 1)  / 2;

        return res;
    }
}

결과가 잘 나왔다!

Reference

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