Solution: Binary Trees With Factors

#algorithms #javascript #java #python

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #823 (Medium): Binary Trees With Factors

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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].

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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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;
    }
};