LeetCode in Kotlin

3164. Find the Number of Good Pairs II

Medium

You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.

A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).

Return the total number of good pairs.

Example 1:

Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

Output: 5

Explanation:

The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).

Example 2:

Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

Output: 2

Explanation:

The 2 good pairs are (3, 0) and (3, 1).

Constraints:

• 1 <= n, m <= 105
• 1 <= nums1[i], nums2[j] <= 106
• 1 <= k <= 103

Solution

class Solution {
    fun numberOfPairs(nums1: IntArray, nums2: IntArray, k: Int): Long {
        val hm = HashMap<Int, Int>()
        var ans: Long = 0
        for (`val` in nums2) {
            hm[`val` * k] = hm.getOrDefault(`val` * k, 0) + 1
        }
        for (index in nums1.indices) {
            if (nums1[index] % k != 0) {
                continue
            }
            var factor = 1
            while (factor * factor <= nums1[index]) {
                if (nums1[index] % factor != 0) {
                    factor++
                    continue
                }
                val factor1 = factor
                val factor2 = nums1[index] / factor
                if (hm.containsKey(factor1)) {
                    ans += hm[factor1]!!.toLong()
                }
                if (factor1 != factor2 && hm.containsKey(factor2)) {
                    ans += hm[factor2]!!.toLong()
                }
                factor++
            }
        }
        return ans
    }
}

This site is open source. Improve this page.