Pairs of Songs With Total Durations Divisible by 60 LeetCode Solution

Problem Statement

Pairs of Songs With Total Durations Divisible by 60 LeetCode Solution – Pairs of Songs With Total Durations Divisible by 60 LeetCode Solution says that – You are given a list of songs where the i^th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input:

 time = [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
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input:

 time = [60,60,60]

Output:

 3

Explanation:

 All three pairs have a total duration of 120, which is divisible by 60.

Constraints:

• 1 <= time.length <= 6 * 10⁴
• 1 <= time[i] <= 500

ALGORITHM –

IDEA –

• In order to find Pairs of Songs With Total Durations Divisible by 60. We will think of the “count pair with given sum ” question. In this question, it is written that sum of pairs is divisible by 60 so we think like -> x = first number,y = second number.
• So, If the sum of numbers is divisible by 60 when the remainder of the sum modulo must be equal to 0.
•                   X%60 + Y%60 = 60.
• So, First, we will update all the elements by modulo 60 and Will check if the sum of numbers is equal to 60 then we will update our Total and at last we will return Total.[Total is the total pair sum equal to 60].

APPROACH –

• At first, we will update our array for each element modulo by 60. Then we will make one hashmap and total which returns the total pair.
• Then will find the frequency of each element by using a hashmap.
• Then again we will run a loop and check for the condition if 60 – element is present in the hashmap within that we will check if 60-element == element(check for element consider more than on time) then update the total by adding count.
• Else we will check for zero which means a multiple of 60 and find the count of total zeroes and add them into the total.
• At last, we will return the total.
• Hence we will count Pairs of Songs With Total Durations Divisible by 60.

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        for i in range(len(time)):
            time[i] %= 60
        
        dic = {}
        for i in time:
            if i in dic:
                dic[i] += 1
                
            else:
                dic[i] = 1
        flag = False        
        count = 0
        for i in range(len(time)):
            if 60-time[i] in dic:
                if 60-time[i] == time[i]:
                    count += dic[60-time[i]]-1
                    
                else:
                    count += dic[60-time[i]]
            
            
            elif time[i] == 0:
                count += dic[0]-1
                
        return count // 2

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int count = 0;
        if (time == null || time.length == 0) return count;
        Map<Integer, Integer> dic = new HashMap<>();
        for (int i = 0; i < time.length; i++) {          
            int rem = time[i]%60;
            count += dic.getOrDefault((60-rem)%60, 0);
            dic.put(rem, dic.getOrDefault(rem, 0) + 1);
        }
        return count;    
    }
}

Complexity Analysis for Pairs of Songs With Total Durations Divisible by 60 LeetCode Solution

TIME COMPLEXITY: O(N), As we have traversed through the whole array 2 times.

SPACE COMPLEXITY: O(N). As we have created one hashmap.

SIMILAR QUESTIONS –  https://tutorialcup.com/interview/dynamic-programming/divisible-pairs-counting.htm