Binary Trees With Factors - Practice Coding Problems

Binary Trees With Factors - Problem

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 large so return the answer modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: arr = [2,4]

› Output: 3

💡 Note: We can make these trees: [2] (root 2), [4] (root 4), and [4,2,2] (root 4 with children 2,2). Since 2×2=4, we can build a tree with root 4 and two children of value 2.

Example 2 — More Factors

$ Input: arr = [2,4,5,10]

› Output: 7

💡 Note: Trees with root 2: [2]. Root 4: [4], [4,2,2]. Root 5: [5]. Root 10: [10], [10,2,5], [10,5,2]. Total = 1 + 2 + 1 + 3 = 7 trees.

Example 3 — Single Element

$ Input: arr = [3]

› Output: 1

💡 Note: Only one tree possible: [3] with single node as root.

Constraints

1 ≤ arr.length ≤ 1000
2 ≤ arr[i] ≤ 10⁹
All the values of arr are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,4] of unique integers > 1

Find Factors

Check which numbers can be products: 4 = 2×2

Count Trees

Total trees: [2], [4], [4,2,2] = 3

Key Takeaway

🎯 Key Insight: Count all possible binary trees where each non-leaf node equals the product of its children

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is that each number can be a tree root if it equals the product of two other numbers in the array. Best approach uses dynamic programming with memoization to count trees efficiently. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(n³ * 2^n)	O(n)	Try all possible tree combinations recursively without optimization
Dynamic Programming with Memoization	O(n³)	O(n)	Cache results to avoid recalculating the same subproblems
Sort and Bottom-Up DP	O(n² + n log n)	O(n)	Sort array first, then build solutions from smallest to largest

Brute Force Recursion — Algorithm Steps

For each number in array, try it as root
Find all pairs (a,b) where a*b equals root
Recursively count trees for left and right subtrees
Multiply counts and sum all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Root

For each number, try it as root

Find Factors

Find all pairs whose product equals root

Recurse

Recursively count subtrees without memoization

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_SIZE 1000

int arr_global[MAX_SIZE];
int arr_size;
int arr_set[MAX_SIZE];
int set_size;

int contains(int val) {
    for (int i = 0; i < set_size; i++) {
        if (arr_set[i] == val) return 1;
    }
    return 0;
}

long long countTrees(int root) {
    if (!contains(root)) return 0;
    
    long long result = 1; // Single node tree
    
    for (int i = 0; i < arr_size; i++) {
        for (int j = 0; j < arr_size; j++) {
            if ((long long)arr_global[i] * arr_global[j] == root) {
                long long leftCount = countTrees(arr_global[i]);
                long long rightCount = countTrees(arr_global[j]);
                result = (result + leftCount * rightCount) % MOD;
            }
        }
    }
    
    return result;
}

int solution(int* arr, int size) {
    arr_size = size;
    set_size = size;
    for (int i = 0; i < size; i++) {
        arr_global[i] = arr[i];
        arr_set[i] = arr[i];
    }
    
    long long total = 0;
    for (int i = 0; i < size; i++) {
        total = (total + countTrees(arr[i])) % MOD;
    }
    
    return (int)total;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[MAX_SIZE];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(arr, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ * 2^n)

For each of n numbers, check n² pairs, with exponential recursive calls

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth proportional to array size

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler