Count Array Pairs Divisible by K LeetCode solution in Java

1
// The condition given to us is (a*b % k==0)
2
// So we can rewrite the above condition that if any factor of k is present in a and any other
3
// factor of k is present in b then their multiplication will be divisble by k
4

5
// so gcd(a,k) * gcd(b,k) % k==0
6

7
class Solution {
8
  public long countPairs(int[] nums, int k) {
9
    long ans = 0;
10
    HashMap<Integer, Integer> hm = new HashMap<>();
11
    for (int val : nums) {
12
      int gcd1 = gcd(val, k);
13

14
      for (int gcd2 : hm.keySet()) {
15
        if ((long) gcd1 * gcd2 % k == 0) {
16
          ans += hm.get(gcd2);
17
        }
18
      }
19

20
      hm.put(gcd1, hm.getOrDefault(gcd1, 0) + 1);
21
    }
22

23
    return ans;
24
  }
25

26
  // function to calculate gcd
27

28
  public int gcd(int n1, int n2) {
29
    while (n1 % n2 != 0) {
30
      int rem = n1 % n2;
31
      n1 = n2;
32
      n2 = rem;
33
    }
34
    return n2;
35
  }
36
}