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.
1import java.util.*;
2
3public class SongPairs {
4 public static int numPairsDivisibleBy60(int[] time) {
5
This Java solution follows the same logic, using an array to store remainder counts, and checks complement pairs for each song in the input.
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 Java solution employs two nested loops to check every possible pair of songs, returning the count of those divisible by 60.