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.
1function numPairsDivisibleBy60(time) {
2 let remainder = new Array(60).fill(0);
3 let count = 0;
4
In this JavaScript version, we maintain an array to track the count of each remainder. Using a for-of loop, we iterate through each song duration and update our result based on the complement of the current remainder value.
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.
The Python brute force approach follows the dual loop structure to test each possible song pair, increasing the count of valid pairs whose total duration is divisible by 60.