2176-CountEqualAndDivisiblePairsInAnArray.go

package main

// 2176. Count Equal and Divisible Pairs in an Array
// Given a 0-indexed integer array nums of length n and an integer k, 
// return the number of pairs (i, j) where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.

// Example 1:
// Input: nums = [3,1,2,2,2,1,3], k = 2
// Output: 4
// Explanation:
// There are 4 pairs that meet all the requirements:
// - nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
// - nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
// - nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
// - nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

// Example 2:
// Input: nums = [1,2,3,4], k = 1
// Output: 0
// Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

// Constraints:
//     1 <= nums.length <= 100
//     1 <= nums[i], k <= 100

import "fmt"

// bucket sort
func countPairs(nums []int, k int) int {
    res, buckets := 0, make([][]int, 101)
    for i, v := range nums {
        buckets[v] = append(buckets[v], i)
    }
    for _, bucket := range buckets {
        if len(bucket) > 1 {
            for i := 0; i < len(bucket) - 1; i++ {
                for j := i + 1; j < len(bucket); j++ {
                    if (bucket[i] * bucket[j]) % k == 0 {
                        res++
                    }
                }
            }
        }
    }
    return res
}

func countPairs1(nums []int, k int) int {
    res, n := 0, len(nums)
    for i := 0; i < n - 1; i++ {
        for j := i + 1; j < n; j++ {
            if nums[i] == nums[j] && (i * j) % k == 0 {
                res++
            }
        }
    }
    return res
}

func main() {
    // Example 1:
    // Input: nums = [3,1,2,2,2,1,3], k = 2
    // Output: 4
    // Explanation:
    // There are 4 pairs that meet all the requirements:
    // - nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
    // - nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
    // - nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
    // - nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.
    fmt.Println(countPairs([]int{3,1,2,2,2,1,3}, 2)) // 4
    // Example 2:
    // Input: nums = [1,2,3,4], k = 1
    // Output: 0
    // Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.
    fmt.Println(countPairs([]int{1,2,3,4}, 1)) // 0

    fmt.Println(countPairs([]int{1,2,3,4,5,6,7,8,9}, 2)) // 0
    fmt.Println(countPairs([]int{9,8,7,6,5,4,3,2,1}, 2)) // 0

    fmt.Println(countPairs1([]int{3,1,2,2,2,1,3}, 2)) // 4
    fmt.Println(countPairs1([]int{1,2,3,4}, 1)) // 0
    fmt.Println(countPairs1([]int{1,2,3,4,5,6,7,8,9}, 2)) // 0
    fmt.Println(countPairs1([]int{9,8,7,6,5,4,3,2,1}, 2)) // 0
}