K Divisible Elements Subarrays LeetCode solution in Java

1
class Solution {
2
  public int countDistinct(int[] nums, int k, int p) {
3
    int n = nums.length;
4
    // we are storing hashcode for all the substrings so that we can compare them faster.
5
    // main goal is to avoid entire sub array comparision using hashcode.
6
    Set<Long> ways = new HashSet<>();
7
    for (int i = 0; i < n; i++) {
8
      int cnt = 0;
9
      long hc = 1; // this is the running hashcode for sub array [i...j]
10
      for (int j = i; j < n; j++) {
11
        hc =
12
            199L * hc
13
                + nums[
14
                    j]; // updating running hashcode, since we nums are <=200, we shall consider a
15
        // prime near 200 to avoid collision
16
        if (nums[j] % p == 0) cnt++;
17
        if (cnt <= k) { // if current subarray [i...j] is valid, add its hashcode in our storage.
18
          ways.add(hc);
19
        }
20
      }
21
    }
22
    return ways.size();
23
  }
24
}