Binary Trees With Factors
MediumArrayHash TableDynamic ProgrammingSorting
Solution
export function numFactoredBinaryTrees(arr: number[]): number {
arr.sort((a, b) => a - b);
const MOD = 10 ** 9 + 7;
const dp = new Map<number, number>();
let answer = 0;
for (const num of arr) {
let total = 1;
for (const [key, value] of dp.entries()) {
if (num % key === 0) {
const otherValue = dp.get(num / key) ?? 0;
total = (total + value * otherValue) % MOD;
}
}
dp.set(num, total);
answer = (answer + total) % MOD;
}
return answer;
}