LIST OF C# SOLUTION FOR SMALL AND LARGE ARRAYS (3 C# Solutions)
Intuition / Approach / ComplexityThis is an easy question, we can have a solution without using dictionary, just a brute force solution, we can iterate all nums
# Intuition / Approach / Complexity
<!-- Describe your first thoughts on how to solve this problem. -->
This is an easy question, we can have a solution without using dictionary, just a brute force solution, we can iterate all nums2 and change the number in nums2 to number * k (this will save time iterating all nums1 numbers and avoid doing multiplication, we just need to see the modulo of numbers from nums1), then we iterate all nums1 and we check the result of the modulo if it's equal to zero to increment our result variable, this will give us a time complexity of O(n * m) and space complexity of O(1).

We can reduce the time complexity to O(n * sqrt(max(nums1)) + m) if we use dictionary storing array nums2 times k having counter of occurance, then we calculate the factors (we can have other additional dictionary storing nums1 if we have duplicated numbers).
This is the case for problem 3164. Find the Number of Good Pairs II, but our problem 3162. Find the Number of Good Pairs I don't have many items in the arrays and duplicated numbers won't make the difference, but the other problem have large arrays which makes the usage of dictionary more usefull.
So I put the Dictionary Solution 1 & Dictionary Solution 2 which works for both problems (the only difference is the return type int and long).
Dictionary Solution 1 have one dictionary to store the nums2 times k with counter (space complexity is O(m)), while Dictionary Solution 2 have two dictionary to store nums2 times k and nums1 with counter(space complexity is O(n + m)).

[Solution For Problem 3164. Find the Number of Good Pairs II](https://leetcode.com/problems/find-the-number-of-good-pairs-ii/solutions/6535575/the-most-optimized-c-solution-explained-runtime-136ms-beats-100-00-memory-79-12mb-beats-100-00/)

# Code
```csharp [Brute Force Solution]
public class Solution {
    public int NumberOfPairs(int[] nums1, int[] nums2, int k) {
        int result = 0;
        for(int j = 0; j < nums2.Length; j++){
            nums2[j] *= k;
            for(int i=0; i<nums1.Length; i++){
                if(nums1[i] % nums2[j] == 0) 
                    result++;
            }
        }
        return result;
    }
}
```

```csharp [Dictionary Solution 1]
public class Solution {
    public int NumberOfPairs(int[] nums1, int[] nums2, int k) {
        int result = 0;
        Dictionary<int, int> f = new();
        for(int i = 0; i < nums2.Length; i++){
            if(!f.ContainsKey(nums2[i] * k))
                f.Add(nums2[i] * k, 1);
            else
                f[nums2[i] * k]++;
        }
        for(int i = 0; i < nums1.Length; i++){
            if(nums1[i] % k != 0)
                continue;
            int number = nums1[i];
            int max = (int)Math.Sqrt(number);
            for (int factor = 1; factor <= max; ++factor)
            {  
                if (number % factor == 0) 
                {
                    result += f.ContainsKey(factor) ? f[factor] : 0;
                    if (factor != number/factor && f.ContainsKey(number/factor))
                        result += f[number/factor];
                }
            }
        }
        return result;
    }
}
```

```csharp [Dictionary Solution 2]
public class Solution {
    public int NumberOfPairs(int[] nums1, int[] nums2, int k) {
        int result = 0;
        Dictionary<int, int> f = new();
        for(int i = 0; i < nums2.Length; i++){
            nums2[i] = nums2[i] * k;
            if(!f.ContainsKey(nums2[i]))
                f.Add(nums2[i], 1);
            else
                f[nums2[i]]++;
        }
        Dictionary<int, int> n1 = new();
        for(int i = 0; i < nums1.Length; i++){
            if(!n1.ContainsKey(nums1[i]))
                n1.Add(nums1[i], 1);
            else
                n1[nums1[i]]++;
        }
        foreach(var kvp in n1){
            if(kvp.Key % k != 0)
                continue;
            int r = 0;
            int max = (int)Math.Sqrt(kvp.Key);
            for (int factor = 1; factor <= max; factor++)
            {  
                if (kvp.Key % factor == 0) 
                {
                    if(f.ContainsKey(factor))
                        r += f[factor];
                    if (factor != kvp.Key/factor && f.ContainsKey(kvp.Key/factor))
                        r += f[kvp.Key/factor];
                }
            }
            result += (r * kvp.Value);
        }
        return result;
    }
}
```
['Array', 'Hash Table', 'Counting', 'Number Theory', 'C#']