title: Binary Trees With Factors
slug: binary-trees-with-factors
difficulty: medium
leetcode_id: 823
leetcode_url: https://leetcode.com/problems/binary-trees-with-factors/
categories:
  - arrays
  - hash-tables
  - dynamic-programming
  - sorting
patterns:
  - slug: dynamic-programming
    is_optimal: true

function_signature: "def num_factored_binary_trees(arr: list[int]) -> int:"

test_cases:
  visible:
    - input: { arr: [2, 4] }
      expected: 3
    - input: { arr: [2, 4, 5, 10] }
      expected: 7
  hidden:
    - input: { arr: [2] }
      expected: 1
    - input: { arr: [2, 3, 5, 7, 11] }
      expected: 5
    - input: { arr: [2, 4, 8] }
      expected: 7
    - input: { arr: [2, 4, 8, 16] }
      expected: 15
    - input: { arr: [2, 3, 6, 18] }
      expected: 7
    - input: { arr: [18, 3, 6, 2] }
      expected: 7
    - input: { arr: [2, 4, 16, 8] }
      expected: 15

description: |
  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`.

constraints: |
  - `1 <= arr.length <= 1000`
  - `2 <= arr[i] <= 10^9`
  - All the values of `arr` are **unique**

examples:
  - input: "arr = [2, 4]"
    output: "3"
    explanation: "We can make these trees: [2], [4], [4, 2, 2]. Each single node counts as a tree, and 4 can be the root with two children of value 2 since 2 * 2 = 4."
  - 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]. Note that [10, 2, 5] and [10, 5, 2] are different trees because the left and right children are swapped."

explanation:
  intuition: |
    Imagine building binary trees like stacking building blocks. Each node can either stand alone (a single-node tree) or become a parent by placing two children beneath it — but only if the parent's value equals the product of its children.

    The key insight is that **the number of trees with a given root depends on the number of trees we can build with its potential children**. If node `x` can have children `a` and `b` (where `a * b = x`), then the number of trees rooted at `x` using this pair equals `trees(a) * trees(b)` — we can combine any tree rooted at `a` with any tree rooted at `b`.

    Think of it like this: for each number in the array, ask "which pairs of numbers from my array multiply to give me this number?" For each valid pair, multiply the number of ways to build the left subtree by the number of ways to build the right subtree.

    This naturally leads to a **bottom-up dynamic programming** approach. If we process numbers in sorted order (smallest to largest), when we reach a number `x`, we've already computed the tree counts for all potential children (since children must be smaller than their product).

  approach: |
    We solve this using **Dynamic Programming with Hash Map**:

    **Step 1: Sort the array and create a lookup structure**

    - Sort `arr` in ascending order so we process smaller values before larger ones
    - Create a hash map `dp` where `dp[x]` represents the number of binary trees with `x` as the root
    - Initially, every number can form a single-node tree, so `dp[x] = 1` for all `x`

    &nbsp;

    **Step 2: Build tree counts bottom-up**

    - For each number `x` in sorted order:
      - For each smaller number `a` in the array:
        - Check if `x` is divisible by `a` (i.e., `x % a == 0`)
        - Calculate `b = x / a`
        - If `b` exists in our array, then `a` and `b` can be children of `x`
        - Add `dp[a] * dp[b]` to `dp[x]` — this counts all ways to combine subtrees rooted at `a` and `b`

    &nbsp;

    **Step 3: Sum all tree counts**

    - Return the sum of all `dp[x]` values, modulo `10^9 + 7`
    - Each `dp[x]` counts trees rooted at `x`, so summing gives total trees

    &nbsp;

    The sorted order guarantees that when computing `dp[x]`, both `dp[a]` and `dp[b]` are already computed (since `a` and `b` are smaller than `x`).

  common_pitfalls:
    - title: Not Counting Left-Right Permutations
      description: |
        When `a != b` and both `a * b = x`, the trees `[x, a, b]` and `[x, b, a]` are distinct because binary trees distinguish between left and right children.

        You might think we need special handling, but iterating through all `a` values naturally handles this: when `a = 2, b = 5` we count `dp[2] * dp[5]`, and when `a = 5, b = 2` we count `dp[5] * dp[2]` — both get added to `dp[10]`.
      wrong_approach: "Only counting each pair once"
      correct_approach: "Let the iteration naturally count both orderings"

    - title: Integer Overflow
      description: |
        With `arr[i]` up to `10^9`, the product of two elements could exceed 32-bit integer limits. Additionally, multiplying tree counts (`dp[a] * dp[b]`) can overflow.

        Apply modulo `10^9 + 7` after each multiplication, not just at the end. Use 64-bit integers or Python's arbitrary precision to avoid overflow during intermediate calculations.
      wrong_approach: "Only applying modulo at the final sum"
      correct_approach: "Apply modulo after each dp multiplication"

    - title: Forgetting Single-Node Trees
      description: |
        Every element in the array can form a valid single-node binary tree, regardless of whether it can be a product of other elements.

        Initialize `dp[x] = 1` for every `x` in the array before computing parent-child relationships. The final answer includes these base cases.
      wrong_approach: "Only counting trees with children"
      correct_approach: "Initialize dp[x] = 1 for all elements"

    - title: Not Sorting First
      description: |
        The DP recurrence relies on children being processed before parents. If we don't sort, we might try to use `dp[a]` before it's fully computed.

        For example, with `arr = [10, 2, 5]`, if we process `10` first, `dp[2]` and `dp[5]` would still be at their initial values, missing any trees built from their factors.
      wrong_approach: "Processing elements in original order"
      correct_approach: "Sort array so smaller elements are processed first"

  key_takeaways:
    - "**Counting with DP**: When counting combinations of substructures, multiply the counts — if left subtree has `L` ways and right has `R` ways, the combined tree has `L * R` ways"
    - "**Hash map for O(1) lookup**: Using a hash map to check if a factor exists in the array turns an O(n) search into O(1)"
    - "**Process in dependency order**: Sorting ensures we compute values for children before we need them for parents — a common DP technique"
    - "**Modular arithmetic**: For problems with large answers, apply modulo after each operation to prevent overflow"

  time_complexity: "O(n^2). After sorting (O(n log n)), for each of the n elements, we iterate through all smaller elements to find valid factor pairs."
  space_complexity: "O(n). We store a hash map with one entry per element in the array."

solutions:
  - approach_name: Dynamic Programming with Hash Map
    is_optimal: true
    code: |
      def num_factored_binary_trees(arr: list[int]) -> int:
          MOD = 10**9 + 7

          # Sort so we process smaller values first
          arr.sort()

          # dp[x] = number of binary trees with root x
          # Every element can be a single-node tree
          dp = {x: 1 for x in arr}

          # Convert to set for O(1) factor lookup
          arr_set = set(arr)

          for x in arr:
              # Try every smaller element as potential left child
              for a in arr:
                  if a >= x:
                      break  # a must be smaller than x

                  # Check if x is divisible by a
                  if x % a == 0:
                      b = x // a
                      # If b exists in array, (a, b) can be children of x
                      if b in arr_set:
                          # Add all combinations of subtrees
                          dp[x] = (dp[x] + dp[a] * dp[b]) % MOD

          # Sum all tree counts
          return sum(dp.values()) % MOD
    explanation: |
      **Time Complexity:** O(n^2) — For each element, we check all smaller elements as potential factors.

      **Space Complexity:** O(n) — Hash map storing tree count for each element.

      We sort the array to ensure children are processed before parents. For each number, we find all pairs of factors from the array and multiply their tree counts. The hash set enables O(1) lookup for the second factor.

  - approach_name: Brute Force with Recursion
    is_optimal: false
    code: |
      def num_factored_binary_trees(arr: list[int]) -> int:
          MOD = 10**9 + 7
          arr_set = set(arr)

          # Memoization cache
          memo = {}

          def count_trees(root: int) -> int:
              """Count trees that can be rooted at 'root'."""
              if root in memo:
                  return memo[root]

              # Base case: single node tree
              total = 1

              # Try all pairs (a, b) where a * b = root
              for a in arr:
                  if root % a == 0:
                      b = root // a
                      if b in arr_set and a != root and b != root:
                          # Recursively count subtrees
                          total = (total + count_trees(a) * count_trees(b)) % MOD

              memo[root] = total
              return total

          # Sum trees rooted at each element
          result = 0
          for x in arr:
              result = (result + count_trees(x)) % MOD

          return result
    explanation: |
      **Time Complexity:** O(n^2) with memoization — Same as the iterative approach, but uses recursion.

      **Space Complexity:** O(n) — Memoization cache plus recursion stack.

      This top-down approach uses recursion with memoization. For each potential root, we recursively count subtrees for all valid child pairs. While conceptually clearer, it has additional overhead from recursion and may hit stack limits for deep recursion. The iterative bottom-up approach is preferred.
