Welcome to Subscribe On Youtube

3162. Find the Number of Good Pairs I

Description

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 <= 50
• 1 <= nums1[i], nums2[j] <= 50
• 1 <= k <= 50

Solutions

Solution 1: Brute Force Enumeration

We directly enumerate all digits $(x, y)$, and check whether $x \mod (y \times k) = 0$. If it is, we increment the answer.

After the enumeration ends, we return the answer.

The time complexity is $O(m \times n)$, where $m$ and $n$ are the lengths of arrays nums1 and nums2 respectively. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript
• Java 2
• C++ 2
• Python 2
• Go 2
• TypeScript 2

• class Solution {
      public int numberOfPairs(int[] nums1, int[] nums2, int k) {
          int ans = 0;
          for (int x : nums1) {
              for (int y : nums2) {
                  if (x % (y * k) == 0) {
                      ++ans;
                  }
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
          int ans = 0;
          for (int x : nums1) {
              for (int y : nums2) {
                  if (x % (y * k) == 0) {
                      ++ans;
                  }
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
          return sum(x % (y * k) == 0 for x in nums1 for y in nums2)
  
  

• func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
  	for _, x := range nums1 {
  		for _, y := range nums2 {
  			if x%(y*k) == 0 {
  				ans++
  			}
  		}
  	}
  	return
  }
  

• function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
      let ans = 0;
      for (const x of nums1) {
          for (const y of nums2) {
              if (x % (y * k) === 0) {
                  ++ans;
              }
          }
      }
      return ans;
  }
  
  

• class Solution {
      public int numberOfPairs(int[] nums1, int[] nums2, int k) {
          Map<Integer, Integer> cnt1 = new HashMap<>();
          for (int x : nums1) {
              if (x % k == 0) {
                  cnt1.merge(x / k, 1, Integer::sum);
              }
          }
          if (cnt1.isEmpty()) {
              return 0;
          }
          Map<Integer, Integer> cnt2 = new HashMap<>();
          for (int x : nums2) {
              cnt2.merge(x, 1, Integer::sum);
          }
          int ans = 0;
          int mx = Collections.max(cnt1.keySet());
          for (var e : cnt2.entrySet()) {
              int x = e.getKey(), v = e.getValue();
              int s = 0;
              for (int y = x; y <= mx; y += x) {
                  s += cnt1.getOrDefault(y, 0);
              }
              ans += s * v;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
          unordered_map<int, int> cnt1;
          for (int x : nums1) {
              if (x % k == 0) {
                  cnt1[x / k]++;
              }
          }
          if (cnt1.empty()) {
              return 0;
          }
          unordered_map<int, int> cnt2;
          for (int x : nums2) {
              ++cnt2[x];
          }
          int mx = 0;
          for (auto& [x, _] : cnt1) {
              mx = max(mx, x);
          }
          int ans = 0;
          for (auto& [x, v] : cnt2) {
              int s = 0;
              for (int y = x; y <= mx; y += x) {
                  s += cnt1[y];
              }
              ans += s * v;
          }
          return ans;
      }
  };
  

• class Solution:
      def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
          cnt1 = Counter(x // k for x in nums1 if x % k == 0)
          if not cnt1:
              return 0
          cnt2 = Counter(nums2)
          ans = 0
          mx = max(cnt1)
          for x, v in cnt2.items():
              s = sum(cnt1[y] for y in range(x, mx + 1, x))
              ans += s * v
          return ans
  
  

• func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
  	cnt1 := map[int]int{}
  	for _, x := range nums1 {
  		if x%k == 0 {
  			cnt1[x/k]++
  		}
  	}
  	if len(cnt1) == 0 {
  		return 0
  	}
  	cnt2 := map[int]int{}
  	for _, x := range nums2 {
  		cnt2[x]++
  	}
  	mx := 0
  	for x := range cnt1 {
  		mx = max(mx, x)
  	}
  	for x, v := range cnt2 {
  		s := 0
  		for y := x; y <= mx; y += x {
  			s += cnt1[y]
  		}
  		ans += s * v
  	}
  	return
  }
  

• function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
      const cnt1: Map<number, number> = new Map();
      for (const x of nums1) {
          if (x % k === 0) {
              cnt1.set((x / k) | 0, (cnt1.get((x / k) | 0) || 0) + 1);
          }
      }
      if (cnt1.size === 0) {
          return 0;
      }
      const cnt2: Map<number, number> = new Map();
      for (const x of nums2) {
          cnt2.set(x, (cnt2.get(x) || 0) + 1);
      }
      const mx = Math.max(...cnt1.keys());
      let ans = 0;
      for (const [x, v] of cnt2) {
          let s = 0;
          for (let y = x; y <= mx; y += x) {
              s += cnt1.get(y) || 0;
          }
          ans += s * v;
      }
      return ans;
  }
  
  

All Problems

All Solutions