Bài toán

Link đến bài toán: 1010. Pairs of Songs With Total Durations Divisible by 60

Phân tích

Nó gần giống bài này này: 1. Two Sum

Ta có thể brute force, hoặc dùng hash table để giải bài này.

Quan sát thấy, map[60 - x%60] sẽ là số bài hát có thể ghép với x để tổng thời gian là bội của 60. Vậy kết quả sẽ là tổng giá trị của map[x%60] với x là thời gian của bài hát.

Giải thuật

Brute force

func numPairsDivisibleBy60(time []int) int {
    res := 0
    for i := 0; i < len(time); i++ {
        for j := i + 1; j < len(time); j++ {
            if (time[i] + time[j]) % 60 == 0 {
                res++
            }
        }
    }
    return res
}

Độ phức tạp: O(n2).

Hash table

func numPairsDivisibleBy60(time []int) int {
    var res int
    var m = make(map[int]int)
    for _, v := range time {
        res += m[(60-v%60)%60]
        m[v%60]++
    }
    return res
}

Độ phức tạp: O(n).