Problem statement:

問題陳述：

In a list of songs, the i-th song has 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 with (time[i] + time[j]) % 60 == 0).

在歌曲列表中，第i首歌曲的持續時間為[i]秒。 返回其總持續時間(以秒為單位)可被60整除的歌曲對數 。 形式上，我們希望索引i <j的數量為( time [i] + time [j])％60 == 0 )。

Example:

例：

    Input array:
10, 20, 30, 60, 80, 110, 120
Output:
Number of such pairs:
2
Pairs are:
10, 110
60, 120

Solution:

解：

Of course, there is a na?ve solution using brute force technique. It's as simple as checking sum for every possible pair with a time complexity of O(n^2).

當然，存在使用暴力技術的幼稚解決方案。 就像檢查每個可能的對的總和一樣簡單，時間復雜度為O(n ^ 2) 。

Efficient solution can be done using mathematical concepts of congruent modulo and combinatorics.

可以使用等價模和組合數學概念來完成有效的解決方案。

Let's revise what are the cases for a pair sum divisible by 60

讓我們修改一下被60整除的對的情況

1. Both the numbers of the pair divisible by 60.

   這對數字都可以被60整除。

2. The sum of their congruent modulo 60 is divisible by 60.

   它們的全模60的和可被60整除。

So actually all the elements of the array can be grouped by congruent modulo.
Since it’s modulo 60.
Maximum remainder can be 59.
Remainders can be any number between 0 to 59.

因此，實際上，數組的所有元素都可以按全模來分組。
由于它是模60。
最大余數可以是59。
余數可以是0到59之間的任何數字。

We actually group all the elements based on modulo value.

實際上，我們根據模值對所有元素進行分組。

1. Declare group[60]={0}; //since their can be 60 possible remainders starting from 0 to 59

   聲明組[60] = {0}； //因為它們可以是0到59之間的60個余數

2. For I in input array

   對于我在輸入數組

   group[i%60]++;

   組[i％60] ++；

In this way our group is formed.
If group[j] is K, that simply means there are K elements in the array for each of them modulo 60 is j

這樣，我們的小組就形成了。
如果group [j]為K ，則僅表示數組中有K個元素，每個元素的模60為j

So after grouping,

所以分組之后

    10, 20, 30, 60, 80, 110, 120
group[10]=1 //10
group[20]=2 //20,80
group[30]=1 //30
group[50]=1 //110
group[0]=2 //60,120

Now we need to pick pairs from the group such that pair sum can be divisible by 60

現在我們需要從組中選擇對，以便對和可以被60整除

How can we pick?

我們如何挑選？

1. Pick any from group[1] and group [59] //for first no remainder is 1, second remainder is 59 (1+59=60, divisible by 60)

   從組[1]和組[59]中選擇任意一個// //首先沒有余數是1，第二個余數是59(1 + 59 = 60，可被60整除)

2. Pick any from group[2] and group [58] //for first no remainder is 2, second remainder is 58 (2+58=60, divisible by 60)

   從組[2]和組[58]中選擇任何一個，//首先沒有余數是2，第二個余數是58(2 + 58 = 60，可被60整除)

3. Pick any from group[3] and group [57] //for first no remainder is 3, second remainder is 57(3+57=60, divisible by 60)

   從組[3]和組[57]中選擇任意一個//首先，沒有余數是3，第二個余數是57(3 + 57 = 60，可被60整除)

......................continue till group[29] and group[31]......................

......................繼續到第[29] 組和第[31]組 。 .....

Now two groups are remaining
group[30] and group[60]
This two groups are independent group
We can pick any two elements from group[30]
Same for group[0]
We are done...

現在剩下兩組
小組[30]和小組[60]
這兩個小組是獨立小組
我們可以從組[30]中選擇任意兩個元素
群組相同[0]
我們完了...

For group[30] and group[0]

對于組[30]和組[0]

Possible combinations are (n/2) where n be the respective values for group[30] and group[0]
And for 1-29 condition
Pick one from first group and one from second group
Which is n1*n2 //n1=first group item no, n2=second group item no

可能的組合是(n / 2) ，其中n是group [30]和group [0]的相應值
對于1-29條件
從第一組中選擇一個，從第二組中選擇一個
這是n1 * n2 // // n1 =第一組項目編號， n2 =第二組項目編號

For the above example

對于上面的例子

Only combination possible is from

只能組合來自

1. group[10] and group[50] //1,1 elements respectively

   group [10]和group [50] // 1,1個元素

2. group[0] //2 elements

   group [0] // 2個元素

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int numPairsDivisibleBy60(vector<int> time) {
//group[60] renamed as a[60]
int count=0;
int a[60]={0};
for(int i=0;i<time.size();i++){
a[time[i]%60]++;
}
int i=1,j=59;
while(i<j){ //for rules 1-29
count+=a[i]*a[j];
i++;
j--;
}
//for group[30] and group[0]
count+=(a[0]*(a[0]-1)/2)+(a[30]*(a[30]-1)/2);
return count;
}
int main(){
int n,item;
cout<<"Number of times to be entered:\n";
cin>>n;
cout<<"Enter times...\n";
vector<int> time;
while(n--){
cin>>item;
time.push_back(item);
}
cout<<"number of such pairs possible is: "
cout<<numPairsDivisibleBy60(time)<<endl;
return 0;
}

Output

輸出量

Number of times to be entered:
7
Enter times...
10 20 30 60 80 110 120
number of such pairs possible is: 2

翻譯自: https://www.includehelp.com/icp/pairs-of-songs-with-total-durations-divisible-by-60.aspx