3164. Find the Number of Good Pairs II

Intuition

To find the total number of good pairs, we need to iterate through the elements of both arrays and check for pairs that satisfy the given condition.

Approach

1. Create two maps to store the frequency of elements in nums1 and nums2.
2. Iterate through nums1 and populate map1 with the frequencies of elements that are divisible by k.
3. Iterate through nums2 and populate map2 with the frequencies of elements.
4. Iterate through the keys in map1 and for each key, iterate through its divisors.
5. For each divisor, if it exists in map2, increment the result by the product of the frequencies of the corresponding elements in both maps.
6. Return the final result.

Complexity

• Time complexity: O(n * sqrt(max(x))) where n is the length of nums1, and max(x) is the maximum value in nums1.
• Space complexity: O(n + m) for the maps map1 and map2.

Code

C++

class Solution {
public:
    long long numberOfPairs(vector& nums1, vector& nums2, int k) {
        unordered_map map1;
        unordered_map map2;

        for (int x : nums1) {
            if (x % k == 0) {
                int f = x / k;
                map1[f]++;
            }
        }

        for (int x : nums2) {
            map2[x]++;
        }

        long long res = 0;
        for (const auto& [x, y] : map1) {
            for (int i = 1; i <= sqrt(x); ++i) {
                if (x % i == 0) {
                    int cur = x / i;
                    if (map2.find(i) != map2.end()) {
                        res += static_cast(map2[i]) * y;
                    }
                    if (cur != i && map2.find(cur) != map2.end()) {
                        res += static_cast(map2[cur]) * y;
                    }
                }
            }
        }

        return res;
    }
};

Python

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        map1 = defaultdict(int)
        map2 = defaultdict(int)

        for x in nums1:
            if x % k == 0:
                f = x // k
                map1[f] += 1

        for x in nums2:
            map2[x] += 1

        res = 0
        for x, y in map1.items():
            for i in range(1, int(math.sqrt(x)) + 1):
                if x % i == 0:
                    cur = x // i
                    if i in map2:
                        res += map2[i] * y
                    if cur != i and cur in map2:
                        res += map2[cur] * y

        return res

Java

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map map1 = new HashMap<>();
        Map map2 = new HashMap<>();

        for (int x : nums1) {
            if (x % k == 0) {
                int f = x / k;
                map1.put(f, map1.getOrDefault(f, 0) + 1);
            }
        }

        for (int x : nums2) {
            map2.put(x, map2.getOrDefault(x, 0) + 1);
        }

        long res = 0;
        for (Map.Entry entry : map1.entrySet()) {
            int x = entry.getKey();
            int y = entry.getValue();
            for (int i = 1; i <= Math.sqrt(x); ++i) {
                if (x % i == 0) {
                    int cur = x / i;
                    if (map2.containsKey(i)) {
                        res += (long) map2.get(i) * y;
                    }
                    if (cur != i && map2.containsKey(cur)) {
                        res += (long) map2.get(cur) * y;
                    }
                }
            }
        }

        return res;
    }
}

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var numberOfPairs = function (nums1, nums2, k) {
  var map1 = new Map();
  var map2 = new Map();

  nums1.forEach((x) => {
    if (x % k === 0) {
      var f = x / k;
      map1.set(f, (map1.get(f) || 0) + 1);
    }
  });

  nums2.forEach((x) => {
    map2.set(x, (map2.get(x) || 0) + 1);
  });

  var res = 0;
  for (var [x, y] of map1) {
    for (var i = 1; i <= Math.sqrt(x); ++i) {
      if (x % i === 0) {
        var cur = x / i;
        if (map2.has(i)) res += map2.get(i) * y;
        if (cur !== i && map2.has(cur)) res += map2.get(cur) * y;
      }
    }
  }
  return res;
};

Go

func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {
    map1 := make(map[int]int)
    map2 := make(map[int]int)

    for _, x := range nums1 {
        if x % k == 0 {
            f := x / k
            map1[f] = map1[f] + 1
        }
    }

    for _, x := range nums2 {
        map2[x] = map2[x] + 1
    }

    var res int64 = 0
    for x, y := range map1 {
        for i := 1; i <= int(math.Sqrt(float64(x))); i++ {
            if x % i == 0 {
                cur := x / i
                if count, ok := map2[i]; ok {
                    res += int64(count * y)
                }
                if cur != i {
                    if count, ok := map2[cur]; ok {
                        res += int64(count * y)
                    }
                }
            }
        }
    }

    return res
}

C#

public class Solution {
    public long NumberOfPairs(int[] nums1, int[] nums2, int k) {
        Dictionary map1 = new Dictionary();
        Dictionary map2 = new Dictionary();

        foreach (int x in nums1) {
            if (x % k == 0) {
                int f = x / k;
                if (map1.ContainsKey(f))
                    map1[f]++;
                else
                    map1[f] = 1;
            }
        }

        foreach (int x in nums2) {
            if (map2.ContainsKey(x))
                map2[x]++;
            else
                map2[x] = 1;
        }

        long res = 0;
        foreach (var entry in map1) {
            int x = entry.Key;
            int y = entry.Value;
            for (int i = 1; i <= Math.Sqrt(x); ++i) {
                if (x % i == 0) {
                    int cur = x / i;
                    if (map2.ContainsKey(i))
                        res += (long)map2[i] * y;
                    if (cur != i && map2.ContainsKey(cur))
                        res += (long)map2[cur] * y;
                }
            }
        }

        return res;
    }
}

Conclusion

The provided solution efficiently computes the total number of good pairs given two integer arrays nums1 and nums2 along with a positive integer k. By utilizing maps to store the frequencies of elements in both arrays and iterating through the keys to find valid pairs, the solution achieves a time complexity of O(n _ m _ sqrt(max(x))) and a space complexity of O(n + m), where n is the length of nums1, m is the length of nums2, and max(x) is the maximum value in nums1. This approach effectively handles the problem's constraints and provides an optimal solution.