1010. Pairs of Songs With Total Durations Divisible by 60

leetcode medium

#array#backtracking#csharp#leetcode#math#medium

Task

Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.

Пример:

Input: time = [30,20,150,100,40]

Output: 3

C# solution

matched/original

public class Solution {
    public int NumPairsDivisibleBy60(int[] time) {
        int[] remainders = new int[60];
        int count = 0;
        
        foreach (int t in time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumPairsDivisibleBy60(vector<int>& time) {
        vector<int>& remainders = new int[60];
        int count = 0;
        
        foreach (int t in time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

Java solution

matched/original

public class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] remainders = new int[60];
        int count = 0;
        
        for (int t : time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

JavaScript solution

matched/original

class Solution {
    numPairsDivisibleBy60(time) {
        const remainders = new Array(60).fill(0);
        let count = 0;
        
        for (const t of time) {
            if (t % 60 === 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

Python solution

matched/original

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        remainders = [0] * 60
        count = 0
        
        for t in time:
            if t % 60 == 0:
                count += remainders[0]
            else:
                count += remainders[60 - t % 60]
            remainders[t % 60] += 1
        
        return count

Explanation

Algorithm

Инициализация и вычисление остатков:

Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями.

Подсчет пар:

Пройдитесь по каждой песне в списке и для каждого элемента:

Вычислите остаток от деления времени песни на 60.

Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).

Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).

Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.

Возврат результата:

Верните общее количество пар.

😎