Introduction

In this blog post, we will explore how to solve the LeetCode problem "3164" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's the solution to the problem:

• Precompute factors: For each number in nums2, precompute the value nums2[j] * k. This avoids repeated multiplication inside the inner loop.
• Iterate and check divisibility: Iterate through nums1. For each element, iterate through the precomputed values and check if the element is divisible.

• Count good pairs: Maintain a count of the good pairs, incrementing it whenever a pair (i, j) satisfies the divisibility condition.

• Runtime Complexity: O(nm), where n is the length of nums1 and m is the length of nums2. Storage Complexity: O(m), due to storing precomputed values of nums2[j] \ k.

Code

    def count_good_pairs(nums1, nums2, k):
    """
    Counts the number of good pairs (i, j) such that nums1[i] is divisible by nums2[j] * k.

    Args:
        nums1: The first list of integers.
        nums2: The second list of integers.
        k: A positive integer.

    Returns:
        The total number of good pairs.
    """

    n = len(nums1)
    m = len(nums2)
    count = 0

    # Precompute nums2[j] * k for each j
    precomputed_values = [nums2[j] * k for j in range(m)]

    for i in range(n):
        for j in range(m):
            if nums1[i] % precomputed_values[j] == 0:
                count += 1

    return count