unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60

link

If \text{time}[i] + \text{time}[j] = 0\ (\text{mod } 60), then \text{time}[i] = -\text{time}[j]\ (\text{mod } 60). So, we keep track how many times we have seen \text{time}[i]\ (\text{mod } 60). While considering \text{time}[j], if we have seen -\text{time}[j]\ (\text{mod } 60) before say m times, then we have m pairs with \text{time}[j] as the second element.

Time: \mathcal{O}(n). Since there are only 60 different remainders (\text{mod } 60), space: \mathcal{O}(1).

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        pair_count = 0
        seen = {}
        for d in time:
            neg_d_mod = -d % 60
            pair_count += seen.get(neg_d_mod, 0)

            d_mod = d % 60
            seen[d_mod] = seen.get(d_mod, 0) + 1
        
        return pair_count

tanvirdotzaman

,

Leave a comment