Count Ways to Make Array With Product LeetCode solution in Java

1
class Solution {
2
  // List of primes upto sqrt(10e4)
3
  int[] PRIMES = {
4
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
5
  };
6
  // Factors of integers upto 13
7
  int[][] SMALL_INT_FACTORS = {
8
    null, {1}, {2}, {3}, {2, 2}, {5}, {2, 3}, {7}, {2, 2, 2}, {3, 3}, {2, 5}, {11}, {2, 2, 3}, {13}
9
  };
10

11
  public int[] waysToFillArray(int[][] queries) {
12
    int n = queries.length;
13
    int[] ans = new int[n];
14
    for (int i = 0; i < n; ++i) ans[i] = dewIt(queries[i]);
15
    return ans;
16
  }
17

18
  private int dewIt(int[] q) {
19
    long ans = 1;
20
    int k = q[0], num = q[1];
21
    for (int p : PRIMES) {
22
      int n = 0; // Power of prime factor within this num
23
      while (num % p == 0) {
24
        num /= p;
25
        ++n;
26
      }
27
      ans = multiply(ans, getSplitCount(n, k));
28
    }
29
    if (num > 1) // If any prime greater than sqrt(10e4) is a remaining factor of num
30
    ans = multiply(ans, k);
31
    return (int) ans;
32
  }
33

34
  // In how many ways can we split an integer n into k non-negative numbers?
35
  // Answer = combin(n+k-1, k-1) (11th grade math; non-trivial but google-able)
36
  // combin(n+k-1, k-1) smoothly turns into combin(n+k-1, n)
37
  private long getSplitCount(int n, int k) {
38
    int a = n + k - 1, b = k - 1;
39
    if ((b << 1) > a) b = a - b;
40
    return comb(a, b);
41
  }
42

43
  // combin(n, r) = (n . n-1 . n-2 . n-3 ... n-r+1)/(1 . 2 . 3 ... r)
44
  // Brute force division:
45
  //   We exploit the fact that r in this problem is at max 13
46
  //   We try to cancel common prime factors of numerator and denominator terms
47
  // This leaves us with numerator elements alone (thus avoiding mod related issues wrt division)
48
  private long comb(int n, int r) {
49
    int[] numerators = new int[r];
50
    for (int i = 0, j = n; i < r; ++i, --j) numerators[i] = j;
51
    for (int i = 2; i <= r; ++i) {
52
      int[] factors = SMALL_INT_FACTORS[i];
53
      for (int f : factors)
54
        for (int j = 0; ; ++j)
55
          if (numerators[j] % f == 0) {
56
            numerators[j] /= f;
57
            break;
58
          }
59
    }
60
    long ans = 1;
61
    for (int num : numerators) ans = multiply(ans, num);
62
    return ans;
63
  }
64

65
  private long multiply(long v, long u) {
66
    return v * u % 1000000007;
67
  }
68
}