“This is the 26th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

The question to describe

In the song list, track I has a duration of time[I] seconds.

Returns the number of song pairs whose total duration, in seconds, is divisible by 60. Formally, we want the index numbers I and j to satisfy I < j and have (time[I] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40] Output: 3 explanation: The total duration of these three pairs can be integer 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: [60,60,60] Output: 3 Explanation: The total duration of all three pairs is 120 and can be rounded by 60.

Tip:

  • 1 <= time.length <= 60000
  • 1 <= time[i] <= 500
Analysis of the

When we see a data set less than or equal to 60000, it’s about 1e5, so the time complexity doesn’t really matter in your n^2. So how do we solve the problem of time? Let’s analyze the problem. When you first store a finite number of integer types, consider using the index of the array to represent them.

  • But if you’re just storing these integers in an array, you’re going to have to walk through the entire array to get a value. It’s easy to make order n^2.
  • But if you use an array index, the time by subscript is O(1).

And we’re looking for pairs where the sum of the remainder is equal to **60. ** the sum of the remainder is equal to 60 which means that their sum is divisible by 60. There’s a special case to consider, where the number we found is divisible by 60, and in that case we need to make a special judgment.

var numPairsDivisibleBy60 = function(time) {
    let yushu=new Array(61).fill(0);
    let res=0,thir=0;
    for(let i in time)
    {
        yushu[time[i]%60] + +; }for(let j=0; j<=30; j++)// Loop controls repetition
    {
      if(j==30||j==0)// Permutation with itself, minus pairing with itself twice, so divide by 2
        thir=thir+(yushu[j]*yushu[j]-yushu[j])/2;
     else// Make sure that the sequence number is the same
       res=res+yushu[j]*yushu[60-j];
    }
    res=res+thir;
    
    return res;
    
};
Copy the code

There’s another way, and we can actually mathematically figure out a formula. n * (n – 1) / 2

var numPairsDivisibleBy60 = function(time) {
    let sum = 0;
    let arr = Array(60).fill(0);
    for(let i = 0; i < time.length; i++) {
        arr[time[i]%60] + =1;
    }
    sum += arr[0] * (arr[0] - 1) / 2;
    sum += arr[30] * (arr[30] - 1) / 2;
    let l = 1, r = 59;
    while(l < r){
        sum += arr[l++] * arr[r--];
    }
    return sum;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤