# 823. Binary Trees With Factors

```
T: O(n^2)
S: O(n)
```

````java
```java
class Solution {
    private static final int MOD = 1000000007;
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr); // num_root = num_left(x) * num_right(root/x)
        Map<Integer, Long> map = new HashMap<>(); 
        for (int a : arr) {
            map.put(a, 1l);
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                int root = arr[i];
                int left = arr[j];
                int right = root/left;
                // if (root == left) { // 如果已經找到根 root 一樣大的因數, 代表不用往下找了(??)
                //     break; 
                // }
                if (root%left == 0 && map.containsKey(right)) {
                    map.put(root, (map.get(root) + map.get(left)*map.get(right)) % MOD );
                }
            }
        }
        long sum = 0l;
        for (long count : map.values()) {
            sum += count;
        }
        return (int)(sum%MOD);
    }
}

/**

T: O(n^2)
S: O(n)


for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
這是為了找對應的因數, 所以跑兩層loop 數字去%數字
           if (root%left == 0
           -> 找到 left 是因數(factor), 而且    root/left 有在 map裏面
           代表找到左右子樹了, 
           root 的count ＋ left相乘right -> 就會是新的count

但如何確定這個left right 不會太早算呢？因為left right都有可能是 root
這就是為什麼要先排序sort, 所以我們是從小的數字先去找的
所以整個結果由小到大產生, 這樣就不會影響到之後的結果

最後把每個root的 count 加起來, 就是答案


2 1 
4 1

2 4
2 4

map(4,  map(4) + map(2)*map(2) = 1 + 1 = 2)

2 1
4 2

add all result -> 1+2 = 3

也就是說

4 本身就1了
/\
2 2. -> 再加上這個結果 -> 1*1 然後 add back to map(4)的map key上
 */
```
````
