The O(n) Club: Pairs of Songs With Total Durations Divisible by 60 — Now That’s What I Call Modulo!

The O(n) Club: Pairs of Songs With Total Durations Divisible by 60 — Now That’s What I Call Modulo!

⚡ TL;DR

If you want to pair up songs so their durations add up to any multiple of 60 (not just 60!), ditch the O(n²) brute force and embrace the magic of counting remainders. Here’s what NOT to do:

// O(n<sup>2</sup>) brute force. Don't do this—unless you're paid by the CPU hour.
int count = 0;
for (int i = 0; i < time.length; ++i)
    for (int j = i + 1; j < time.length; ++j)
        if ((time[i] + time[j]) % 60 == 0) count++;

🧠 How Devs Usually Mess This Up

Let me guess—your first thought was to loop through every pair like you’re at a speed-dating event for songs. Classic. Then maybe you started filtering only 60s, or paired everything twice. Maybe you forgot 0 and 30 love themselves? These are the usual wrong turns:

• Assuming song pairs must be adjacent. They don’t. The only thing they must be is divisible by 60.
• Assuming only exact multiples of 60 count. Sorry, 20 + 40 is just as valid as 30 + 150.
• Double counting or missing r=0 / r=30, which are self-pairable (mirror selfies for remainders).
• Using a HashMap instead of a handy-dandy array of size 60. Java arrays: for when you want speed and don’t need to impress anyone with an object graph.

🔍 What’s Actually Going On

Every song duration t can be filed under one of 60 remainder bins (t % 60). For each song, its dream pairing is the one where its remainder plus your current song’s remainder fills a 60 bucket—so if you’re remainder 13, you want 47. If you’re 0, you want another 0 (twinning). If you’re 30, you want… you guessed it, another 30 (midlife crisis friendship).

The trick: count how many times each remainder appears. Then, for each magical pair (r, 60–r), multiply their counts to get the number of unique pairs. For those self-pairers (0, 30), use combinations: count[r] * (count[r] - 1) / 2—basic high school math, only this time you might care.

🛠️ PseudoCode

• Step 1: Make an array int[] count = new int[60]; to stash remainders. No HashMaps here, just reliable old Java arrays.
• Step 2: For each song duration, increment count[current % 60]. Track ‘em all.
• Step 3: For r in 1..29, count all count[r] * count[60 - r] pairs. Each pair is unique, and you won’t double count—promise.
• Step 4: For the remainder weirdos (0 and 30), count pairs with count[r] * (count[r] - 1) / 2—every pair forms an awkward handshake.
• Step 5: Sum it up. You now have the answer, and possibly a restored faith in arrays.

💻 The Code

public int numPairsDivisibleBy60(int[] time) {
    int[] count = new int[60];
    for (int t : time) {
        count[t % 60]++;
    }
    int pairs = 0;
    for (int r = 1; r < 30; r++) {
        pairs += count[r] * count[60 - r];
    }
    pairs += count[0] * (count[0] - 1) / 2;
    pairs += count[30] * (count[30] - 1) / 2;
    return pairs;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Cases: All zeros? All thirties? Just one lonely banger? Works fine, but watch for off-by-one sadness.
• Not Just Neighbors: Any (i < j) pair is legal—adjacency is not required. Welcome to Big O(n) Club.
• Complement Pairing: Don’t mess up r = 0 and r = 30. Their complements are themselves, not any other mystical number.
• Complexity: O(n) time (walk once, sum sixty buckets), O(1) space. If you can count to 60, you can solve this problem.

🧠 Interviewer Brain-Tattoo

“If a problem smells like pairing & modular arithmetic, look for modular complements. And don’t forget: 30 is its own BFF.”