Find the Number of Good Pairs II

To improve upon the brute-force method, we can avoid re-scanning nums2 for every element of nums1. We can pre-process nums2 by storing its elements and their frequencies in a hash map. Then, for each element num1 in nums1, we find all its divisors. For each divisor d, we check if it could be formed by some num2 * k. This is true if d is a multiple of k. If so, we calculate the required num2 value (d/k) and add its frequency from the map to our total count.

• Create a frequency map, freq2, for all numbers in nums2. A HashMap is a good choice for this.
• Initialize a counter goodPairsCount to 0.
• Iterate through each number num1 in nums1.
• For each num1, find all of its divisors. This can be done by iterating from 1 up to sqrt(num1).
• If i divides num1, then both i and num1 / i are divisors.
• For each divisor d found:
  • Check if d is divisible by k.
  • If d % k == 0, calculate val = d / k.
  • Look up val in freq2. If it exists, add its frequency freq2.get(val) to goodPairsCount.
• Be careful to handle perfect squares (when i * i == num1) to avoid double-counting.
• Return goodPairsCount.

The core idea is to change the check from num1 % (num2 * k) == 0 to finding divisors of num1. If d is a divisor of num1, we need to see if d can be represented as num2 * k for some num2 that exists in the nums2 array. This is equivalent to checking if d is divisible by k and if d/k is a number present in nums2.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> freq2 = new HashMap<>();
        for (int num : nums2) {
            freq2.put(num, freq2.getOrDefault(num, 0) + 1);
        }

        long goodPairsCount = 0;
        for (int num1 : nums1) {
            for (int d = 1; d * d <= num1; d++) {
                if (num1 % d == 0) {
                    // d is a divisor
                    if (d % k == 0) {
                        int val = d / k;
                        goodPairsCount += freq2.getOrDefault(val, 0);
                    }
                    
                    // num1 / d is another divisor
                    int d2 = num1 / d;
                    if (d * d != num1) { // Avoid double counting for perfect squares
                        if (d2 % k == 0) {
                            int val = d2 / k;
                            goodPairsCount += freq2.getOrDefault(val, 0);
                        }
                    }
                }
            }
        }
        return goodPairsCount;
    }
}