823. Binary Trees With Factors

leetcode

#array#bit-manipulation#csharp#dynamic-programming#hash-table#leetcode#sort#tree#two-pointers

Task

: medium

Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1.

Мы создаем бинарное дерево, используя эти числа, и каждое число может быть использовано любое количество раз. Значение каждого не листового узла должно быть равно произведению значений его дочерних узлов.

Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7.

Пример:

Input: arr = [2,4]

Output: 3

Explanation: We can make these trees: [2], [4], [4, 2, 2]

C# solution

matched/original

public class Solution {
    public int NumFactoredBinaryTrees(int[] A) {
        const int MOD = 1_000_000_007;
        Array.Sort(A);
        var dp = new long[A.Length];
        Array.Fill(dp, 1);
        var index = new Dictionary<int, int>();
        
        for (int i = 0; i < A.Length; i++) {
            index[A[i]] = i;
        }
        
        for (int i = 0; i < A.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.ContainsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        foreach (long x in dp) {
            result = (result + x) % MOD;
        }
        return (int)result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumFactoredBinaryTrees(vector<int>& A) {
        const int MOD = 1_000_000_007;
        sort(A.begin(), A.end());
        var dp = new long[A.size()];
        Array.Fill(dp, 1);
        var index = new unordered_map<int, int>();
        
        for (int i = 0; i < A.size(); i++) {
            index[A[i]] = i;
        }
        
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.count(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        foreach (long x in dp) {
            result = (result + x) % MOD;
        }
        return (int)result;
    }
}

Java solution

matched/original

class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        int MOD = 1_000_000_007;
        Arrays.sort(A);
        long[] dp = new long[A.length];
        Arrays.fill(dp, 1);
        Map<Integer, Integer> index = new HashMap<>();
        
        for (int i = 0; i < A.length; i++) {
            index.put(A[i], i);
        }
        
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        for (long x : dp) {
            result = (result + x) % MOD;
        }
        return (int) result;
    }

JavaScript solution

matched/original

var numFactoredBinaryTrees = function(A) {
    const MOD = 1_000_000_007;
    A.sort((a, b) => a - b);
    const dp = new Array(A.length).fill(1);
    const index = new Map();
    
    A.forEach((x, i) => index.set(x, i));
    
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < i; j++) {
            if (A[i] % A[j] === 0) {
                let right = A[i] / A[j];
                if (index.has(right)) {
                    dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                }
            }
        }
    }
    
    return dp.reduce((a, b) =>

Python solution

matched/original

class Solution:
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        A.sort()
        dp = [1] * len(A)
        index = {x: i for i, x in enumerate(A)}
        
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0:
                    right = x // A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

Go solution

matched/original

func numFactoredBinaryTrees(A []int) int {
    const MOD = 1_000_000_007
    sort.Ints(A)
    dp := make([]int64, len(A))
    for i := range dp {
        dp[i] = 1
    }
    index := make(map[int]int)
    for i, x := range A {
        index[x] = i
    }

    for i, x := range A {
        for j := 0; j < i; j++ {
            if x%A[j] == 0 {
                right := x / A[j]
                if k, ok := index[right]; ok {
                    dp[i] = (dp[i] + dp[j]*dp[k]) % MOD
                }
            }
        }
    }

    result := int64(0)
    for _, x := range dp {
        result = (result + x) % MOD
    }
    return int(result)
}

Explanation

Algorithm

Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.

Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.

После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.

😎