Sponsored
Sponsored
This approach uses the idea of complementary remainders. If the sum of the remainders of two numbers when divided by 60 equals 60, then their sum is divisible by 60. For example, if the remainder of a number A is 10, you would need a number B whose remainder is 50 to ensure their sum is divisible by 60 (since 10 + 50 = 60).
We can leverage this by keeping a count of all remainders encountered so far and for each number, check for its complement remainder that, when added, will result in a number divisible by 60.
Time Complexity: O(N), where N is the number of songs.
Space Complexity: O(1), since we use a fixed-size array of size 60.
1def numPairsDivisibleBy60(time):
2 remainder = [0] * 60
3 count = 0
4 for t in time:
5 rem =
The Python implementation uses a list to count remainders and checks for the complementary remainder during each iteration to find the required number of pairs.
In this approach, we use a brute force double loop to compare each pair of songs. For each song, pair it with every other song that comes after it and check if their total duration is divisible by 60. This is a straightforward method but inefficient for large inputs.
Although simple, this method is not optimal for large datasets but can work if constraints are smaller.
Time Complexity: O(N^2), iterating over every possible pair.
Space Complexity: O(1), with no additional space used apart from the input array.
This JavaScript version uses a nested for loop to process each possible pair of songs, accumulating counts of pairs whose combined duration is a multiple of 60.