Solution: Binary Trees With Factors
Tags: algorithms, javascript, java, python
Published: 2021-03-13 10:19:11

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/binary-trees-with-factors/discuss/1107268).*

---

#### [Leetcode Problem #823 (*Medium*): Binary Trees With Factors](https://leetcode.com/problems/binary-trees-with-factors/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given an array of unique integers, `arr`, where each integer `arr[i]` is strictly greater than `1`.
>
We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.
>
Return the number of binary trees we can make. The answer may be too large so return the answer __modulo__ `10^9 + 7`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|arr = [2,4]
Output:|3
Explanation:|We can make these trees: [2], [4], [4, 2, 2]
>
Example 2:||
|---:|---|
Input:|arr = [2,4,5,10]
Output:|7
Explanation:|We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

---

#### ***Constraints:***
>
 - `1 <= arr.length <= 1000`
 - `2 <= arr[i] <= 10^9`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The trick to this problem is realizing that we can break it down into smaller pieces. A number can always be a leaf, so the number of **ways** it can form a branch should always start at **1**.

If the number can be made from multiple factor pairs, then **ways** is our starting value of **1** plus the sum of all the ways to make those factor pairs. 

For each existing factor pair (**fA** & **fB**), the number of ways to make that that particular pair configuration is the product of the number of ways to make **fA** and **fB**.

So we can see that each number relies on first solving the same question for each of its factors. This means that we should start by sorting our numbers array (**A**). Then we can iterate through **A** and figure out each number in ascending order, so that we will have completed any factors for larger numbers before we need to use them.

This means storing the information, which we can do in a **map**, so that we can look up the results by value.

In order to be more efficient when we attempt to find each factor pair, we only need to iterate through **A** up to the **square root** of the number in question, so that we don't duplicate the same factor pairs going the opposite direction. That means we need to double every pair result where **fA** and **fB** are not the same.

Since each number can be the head of a tree, our answer (**ans**) will be the sum of each number's result. We shouldn't forget to modulo at each round of summation.

---

#### ***Implementation:***

Java and C++, having typed variables, should use **long** for **ways** and **ans**, but will need to cast **ans** back to **int** before returning. They will also need an extra **continue** conditional when checking for factors.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var numFactoredBinaryTrees = function(A) {
    A.sort((a,b) => a - b)
    let len = A.length, fmap = new Map(), ans = 0
    for (let i = 0; i < len; i++) {
        let num = A[i], ways = 1, lim = Math.sqrt(num)
        for (let j = 0, fA = A[0]; fA <= lim; fA = A[++j]) {
            let fB = num / fA
            if (fmap.has(fB))
                ways += fmap.get(fA) * fmap.get(fB) * (fA === fB ? 1 : 2)
        }
        fmap.set(num, ways), ans += ways
    }
    return ans % 1000000007
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        fmap, ans = defaultdict(), 0
        for num in A:
            ways, lim = 1, sqrt(num)
            for fA in A:
                if fA > lim: break
                fB = num / fA
                if fB in fmap:
                    ways += fmap[fA] * fmap[fB] * (1 if fA == fB else 2)
            fmap[num], ans = ways, (ans + ways)
        return ans % 1000000007
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        Arrays.sort(A);
        int len = A.length;
        long ans = 0;
        HashMap<Integer, Long> fmap = new HashMap<>();
        for (int num : A) {
            long ways = 1;
            double lim = Math.sqrt(num);
            for (int j = 0, fA = A[0]; fA <= lim; fA = A[++j]) {
                if (num % fA != 0) continue;
                int fB = num / fA;
                if (fmap.containsKey(fB))
                    ways += fmap.get(fA) * fmap.get(fB) * (fA == fB ? 1 : 2);
            }
            fmap.put(num, ways);
            ans = (ans + ways) % 1000000007;
        }
        return (int)ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        sort(A.begin(), A.end());
        int len = A.size();
        long ans = 0;
        unordered_map<int, long> fmap;
        for (int num : A) {
            long ways = 1;
            double lim = sqrt(num);
            for (int j = 0, fA = A[0]; fA <= lim; fA = A[++j]) {
                if (num % fA != 0) continue;
                int fB = num / fA;
                if (fmap.find(fB) != fmap.end())
                    ways += fmap[fA] * fmap[fB] * (fA == fB ? 1 : 2);
            }
            fmap[num] = ways;
            ans = (ans + ways) % 1000000007;
        }
        return (int)ans;
    }
};
```