Find the Number of Good Pairs II

• 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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {6        Map<Integer, Integer> freq2 = new HashMap<>();7        for (int num : nums2) {8            freq2.put(num, freq2.getOrDefault(num, 0) + 1);9        }10 11        long goodPairsCount = 0;12        for (int num1 : nums1) {13            for (int d = 1; d * d <= num1; d++) {14                if (num1 % d == 0) {15                    // d is a divisor16                    if (d % k == 0) {17                        int val = d / k;18                        goodPairsCount += freq2.getOrDefault(val, 0);19                    }20                    21                    // num1 / d is another divisor22                    int d2 = num1 / d;23                    if (d * d != num1) { // Avoid double counting for perfect squares24                        if (d2 % k == 0) {25                            int val = d2 / k;26                            goodPairsCount += freq2.getOrDefault(val, 0);27                        }28                    }29                }30            }31        }32        return goodPairsCount;33    }34}

• Initialize a counter goodPairsCount to 0.
• Use a nested loop structure. The outer loop iterates through each element num1 in nums1.
• The inner loop iterates through each element num2 in nums2.
• Inside the inner loop, calculate the potential divisor d = (long)num2 * k to prevent integer overflow.
• Check if num1 is divisible by d using the modulo operator: num1 % d == 0.
• If the condition is true, increment goodPairsCount.
• After both loops complete, return goodPairsCount.

This method involves checking every single pair (i, j) where i is an index for nums1 and j is an index for nums2. For each pair, we explicitly compute nums2[j] * k and then check if nums1[i] is perfectly divisible by this result. We maintain a running total of the pairs that satisfy this condition.

1class Solution {2    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {3        long goodPairsCount = 0;4        for (int i = 0; i < nums1.length; i++) {5            for (int j = 0; j < nums2.length; j++) {6                long divisor = (long) nums2[j] * k;7                // The problem states k is positive, so divisor will not be zero.8                if (nums1[i] % divisor == 0) {9                    goodPairsCount++;10                }11            }12        }13        return goodPairsCount;14    }15}

• First, create a frequency map for the numbers in nums2. A HashMap is suitable.
• Find the maximum value maxVal present in nums1.
• Create a frequency array freq1 of size maxVal + 1 and populate it with the counts of each number from nums1.
• Initialize a counter goodPairsCount to 0.
• Iterate through each unique number num2 and its count c2 from the nums2 frequency map.
• For each num2, calculate val = (long)num2 * k.
• If val exceeds maxVal, we can skip it, as no number in nums1 can be a multiple of it.
• Iterate through all multiples of val starting from val itself, up to maxVal (i.e., m = val, 2*val, 3*val, ...).
• For each multiple m, it represents a valid num1. We find how many times m appears in nums1 using freq1[m].
• Add the product (long)freq1[m] * c2 to goodPairsCount.
• Return the final goodPairsCount.

We begin by creating frequency maps for both arrays. Let freq1 be the frequency map for nums1 and freq2 for nums2. The key insight is to iterate through the smaller set of unique values. We iterate through each unique num2 from freq2. For each num2, we calculate val = num2 * k. Now, the problem is to count how many numbers in nums1 are multiples of val. With freq1 pre-computed, we can find this by summing up the frequencies of val, 2*val, 3*val, etc., up to the maximum value in nums1. The total count for a given num2 is this sum multiplied by the frequency of num2.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {6        Map<Integer, Integer> freq2 = new HashMap<>();7        for (int num : nums2) {8            freq2.put(num, freq2.getOrDefault(num, 0) + 1);9        }10 11        int maxVal = 0;12        for (int num : nums1) {13            if (num > maxVal) {14                maxVal = num;15            }16        }17        18        if (maxVal == 0) { // Edge case for empty nums1 or nums1 with only 0s19            return 0;20        }21 22        int[] freq1 = new int[maxVal + 1];23        for (int num : nums1) {24            freq1[num]++;25        }26 27        long goodPairsCount = 0;28        for (Map.Entry<Integer, Integer> entry : freq2.entrySet()) {29            int num2 = entry.getKey();30            int count2 = entry.getValue();31            32            long val = (long) num2 * k;33 34            for (long multiple = val; multiple <= maxVal; multiple += val) {35                goodPairsCount += (long) freq1[(int)multiple] * count2;36            }37        }38        return goodPairsCount;39    }40}