Binary Trees With Factors LeetCode solution in Java

1
class Solution {
2
  int mod = 1000000007;
3
  HashMap<Integer, Long> dp;
4
  HashSet<Integer> set;
5

6
  public int numFactoredBinaryTrees(int[] arr) {
7
    long ans = 0;
8
    dp = new HashMap<>();
9
    set = new HashSet<>();
10

11
    for (int val : arr) set.add(val);
12

13
    for (int val : arr) {
14
      // giving each unique value a chance to be root node of the tree
15
      ans += solve(val, arr);
16
      ans %= mod;
17
    }
18

19
    return (int) ans;
20
  }
21

22
  public long solve(int val, int[] nums) {
23

24
    if (dp.containsKey(val)) {
25
      return dp.get(val);
26
    }
27

28
    long ans = 1;
29

30
    for (int i = 0; i < nums.length; i++) {
31
      if (val % nums[i] == 0 && set.contains(val / nums[i])) {
32
        long left = solve(nums[i], nums);
33
        long right = solve(val / nums[i], nums);
34

35
        ans += ((left * right) % mod);
36
        ans %= mod;
37
      }
38
    }
39

40
    dp.put(val, ans);
41

42
    return ans;
43
  }
44
}