Binary Trees With Factors

MediumDynamic Programming1d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array arr of distinct integers, each greater than 1. Build binary trees where every node holds a value from arr (values may be reused any number of times), subject to one rule: every non-leaf node has exactly two children, and its value equals the **product** of its two children's values. Two trees are different if their shapes or any node values differ; in particular, swapping the left and right children of a node gives a different tree when the children differ. Return the number of such trees. Because the answer can be very large, return it modulo 10^9 + 7.

Examples

Input: arr = [2,4]
Output: 3
The trees are `[2]`, `[4]`, and `[4,2,2]`.
Input: arr = [2,4,5,10]
Output: 7
Four single nodes, `[4,2,2]`, `[10,2,5]`, and `[10,5,2]`.

Constraints

  • `1 <= arr.length <= 1000`
  • `2 <= arr[i] <= 10^9`
  • All values of `arr` are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 1d dp problems