leetcode-6-1-2021

Posted on In

This is a record of my craking process for Leetcode.

1. Pairs of Songs With Total Durations Divisible by 60 (#1010)#

1.1 Problem Description#

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.

1.2 Soulution#

The most straight-forward way to solve this problem is using two loops which takes $n^2$ time. To optimize it, we can use the same way with two sum, but do a small modification. Since we only need to output the pairs, we use an array (size of 60) to record the current value % 60. Then while in the for-loop, we can check 60 - current_value % 60, get its occurences.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] remains = new int[60];
        int count = 0;
        for(int t : time) {
            if (t % 60 == 0) {
                count += remains[0];
            } else {
                count += remains[60 - t % 60];
            }
            remains[t % 60]++;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
    pub fn num_pairs_divisible_by60(time: Vec<i32>) -> i32 {
        let mut remains = vec![0;60];
        let mut count = 0;
        for t in time.iter() {
            if (t % 60 == 0) {
                count += remains[0];
            } else {
                count += remains[(60 - t % 60) as usize];
            }
            remains[(t % 60) as usize] += 1
        }
        count
    }
}