---

1. Problem Summary

You are given an integer array time, where each element represents the duration of a song in seconds.

Your task is to determine how many pairs (i, j) exist such that:

i < j
(time[i] + time[j]) % 60 == 0

Important details:

• Each pair counts only once
• Order of songs doesn’t matter except i < j constraint
• Durations may vary from small to large values

Example:

Input:  [30,20,150,100,40]
Valid pairs:
(30,150) → 180 % 60 = 0
(20,40)  → 60 % 60 = 0
(20,100) → 120 % 60 = 0
Output: 3

---

2. Key Insights

Insight 1: Modulo remainder drives the condition

Instead of checking sums, we examine:

remainder = time[i] % 60

Insight 2: Complement remainder rule

For a pair to sum to a multiple of 60, we need:

remainderA + remainderB == 60

Special cases:

• remainder = 0 pairs with remainder = 0
• remainder = 30 pairs with remainder = 30

Insight 3: Count frequency of remainders

There are only 60 possible remainders (0–59).

Insight 4: Pair counting via combinations

For normal remainders:

pairs += count[r] * count[60 - r]

For special remainders (0 and 30):

pairs += count[r] * (count[r] - 1) / 2

Insight 5: We only need counts, not explicit pair listings

---

3. Approach

Count remainders and compute valid combinations

Steps:

1. Create array remainderCount[60]
2. For each duration, compute r = time[i] % 60 and increment remainder count
3. Initialize totalPairs = 0
4. Add:
   • combinations of remainder 0 with itself
   • combinations of remainder 30 with itself
5. For r from 1 to 29:
   • add count[r] * count[60 – r] to totalPairs
6. Return totalPairs

---

4. Time and Space Complexity

Time Complexity:

O(N)

Single pass through input and fixed remainder loop.

Space Complexity:

O(1)

Remainder array always size 60.

---

5. Java Solution

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] remainderCount = new int[60];

        for (int t : time) {
            remainderCount[t % 60]++;
        }

        int pairs = 0;

        pairs += remainderCount[0] * (remainderCount[0] - 1) / 2;

        pairs += remainderCount[30] * (remainderCount[30] - 1) / 2;

        for (int r = 1; r < 30; r++) {
            pairs += remainderCount[r] * remainderCount[60 - r];
        }

        return pairs;
    }
}

---

6. Dry Run Examples

Example 1

Input:

[30,20,150,100,40]

Remainders:

30,20,30,40,40

Counts:

count[20]=1
count[30]=2
count[40]=2

Pairs:

30 with 30 → 1
20 with 40 → 2 pairs
Total = 3

Output:

3

---

Example 2

Input:

[60,60,60]

Remainders:

0,0,0

count[0] = 3
Pairs = 3C2 = 3

Output:

3

---

Example 3

Input:

[10,50,90,30]

Remainders:

10,50,30,30

Pairs:
10 + 50 → valid
30 + 30 → valid

Output:

2

---

Example 4

Input:

[1,2,3,4,5]

No valid pairs

Output:

0

---

Example 5

Input:

[15,45,75,105]

All remainders = 15
But only pairs formed if complement exists
No complement remainder 45? Actually yes:
45 is present → pairs formed:

(15,45), (15,75?), (45,75?) etc compute:

Remainders:
15,45,15,45

Pairs:
15 pairs with 45:
2 * 2 = 4

Output:

4

---

7. Why This Solution Works

• Converts problem into modular arithmetic
• Uses complement pairing technique
• Avoids O(N²) brute force
• Constant memory footprint
• Handles large inputs efficiently

---

8. Common Mistakes

1. Forgetting special cases: remainder 0 and 30
2. Double-counting pairs
3. Using nested loops (too slow)
4. Incorrect modulo for negative numbers (not applicable here)
5. Including i == j pairs (not allowed)