Solution For Pairs Of Songs With Total Durations Divisible By 60

Problem Statement:

You are given a list of songs where each song has a duration represented as an integer in seconds. Return the number of pairs of distinct songs such that their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (duration[i] + duration[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]

Output: 3

Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180, index[0, 2], (time[1] = 20, time[3] = 100): total duration 120, index[1, 3], (time[1] = 20, time[4] = 40): total duration 60, index[1, 4].

Solution:

To solve this problem, it is important to recognize that if the remainder of the sum of two durations is equal to zero when divided by 60, then we can say that both durations are divisible by 60. So, we can create a frequency counter that keeps track of the number of durations that have a remainder of time % 60 equal to each possible value from 0 to 59.

We can then loop through the input list, and for each duration, we can calculate the complement duration that we need to find a pair with a total duration divisible by 60. The complement duration would be 60 minus the remainder of the current duration when divided by 60. We can check the frequency counter for the complement duration, and add the number of pairs of durations if it exists in the counter.

Detailed Steps:

1. Initialize the frequency counter to 0 for all possible values of time % 60 from 0 to 59.

2. Loop through the input list and for each duration, do the following:

   • Calculate the remainder of the duration when divided by 60: current_remainder = duration % 60.
   • Calculate the complement duration: complement_duration = (60 – current_remainder) % 60.
   • Add the frequency count of the complement_duration to the number of pairs with a total duration divisible by 60.

3. Return the total number of pairs that have a total duration divisible by 60.

Here’s the Python implementation of the above algorithm:

def numPairsDivisibleBy60(time):
# Initialize the frequency counter
remainder_count = [0] * 60

# Loop through the input list and count the remainders
total_pairs = 0
for duration in time:
    current_remainder = duration % 60
    complement_duration = (60 - current_remainder) % 60
    total_pairs += remainder_count[complement_duration]
    remainder_count[current_remainder] += 1

return total_pairs

Example

time = [30,20,150,100,40] print(numPairsDivisibleBy60(time)) # Output: 3

Time Complexity: O(n), where n is the length of the input list.
Space Complexity: O(1), as we are using a fixed-size frequency counter of length 60.

Step by Step Implementation For Pairs Of Songs With Total Durations Divisible By 60

/**
 * Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

 

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.
Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
 

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
 */

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length; 
        int[] odd = new int[n]; 
        int ans = 0; 
        
        int count = 0; 
        
        for(int i = 0; i < n; i++) {
            if((nums[i] & 1) == 1) {
                count++; 
            }
            
            if(count == k) {
                ans++; 
            }
            
            if(count > k) {
                int left = odd[count - k - 1]; 
                ans += (i - left); 
            }
            
            odd[count] = i; 
        }
        
        return ans; 
    }
}

def numPairsDivisibleBy60(self, time: List[int]) -> int: 

# create an empty dictionary 

dict = {} 

# initialize count to 0 

count = 0

# do for each element 

for i in range(0, len(time)): 

# find the remainder 

rem = time[i] % 60

# if the remainder is 0 

# then increase the count by 

# the value of dictionary at 

# key 0 

if (rem == 0): 

count = count + dict[0] 

# if dictionary contains the 

# value rem-60 then increase 

# the count by the value of 

# dictionary at key (rem-60) 

if (dict.get(60 - rem) != None): 

count = count + dict[60 - rem] 

# if value not found in the 

# dictionary then insert the 

# value in the dictionary 

dict[rem] = dict.get(rem, 0) + 1

# return the count 

return count

var nums = [30,20,150,100,40];
var result = [];

for (var i = 0; i < nums.length; i++) {
    for (var j = i+1; j < nums.length; j++) {
        if ((nums[i] + nums[j]) % 60 === 0) {
            result.push([i, j]);
        }
    }
}

console.log(result);

class Solution {
public:
    int numPairsDivisibleBy60(vector& time) {
        int ans = 0, n = time.size();
        vector cnt(60);
        for (int i = 0; i < n; ++i) {
            ans += cnt[(600 - time[i] % 600) % 600];
            ++cnt[time[i] % 600];
        }
        return ans;
    }
};

using System; 
using System.Collections.Generic; 

public class Solution { 

public int NumPairsDivisibleBy60(int[] time) { 

// create a hashmap to store the remainder of each number when divided by 60 

Dictionary map = new Dictionary(); 

// initialize count to 0 

int count = 0; 

// loop through each number in the array 

foreach(int num in time) { 

// calculate the remainder when divided by 60 

int remainder = num % 60; 

// if the map already contains the key (remainder), 

// that means we have found a pair 

if(map.ContainsKey(remainder)) { 

// so increment the count by the value of the key (remainder) 

count += map[remainder]; 

} 

// if the map does not contain the key (remainder), 

// that means we have not found a pair yet 

else { 

// so add the key (remainder) to the map with value 1 

map.Add(remainder, 1); 

} 

} 

// return the count 

return count; 

} 

}