Count Triplets

  • + 0 comments

    can be solved in O(n)

    func countTriplets(arr []int64, r int64) int64 {
        pair := map[int64]int{}
        triple := map[int64]int{}
        count := 0
        for _, v := range arr{
            if c, ok := triple[v]; ok{
                count += c
            }
            if c, ok := pair[v]; ok{
                triple[v*r] += c
            }
            pair[v*r]++
        }
        return int64(count)
    }