aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_factors.c
blob: 378d28381a297a70c7492fd12f012d0e44bc876e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 823. Binary Trees With Factors
#include "leetcode.h"

/*
 * 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 to fit in a signed 32
 * bit integer, so return the answer modulo 10e9+7
 */

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int numFactoredBinaryTrees(int *arr, int arr_size) {
  int ans = 0, mod = 1e9 + 7;
  qsort(arr, arr_size, sizeof(int), cmp);
  long dp[arr_size];
  for (int i = 0; i < arr_size; i++)
    dp[i] = 1;
  for (int i = 0; i < arr_size; i++) {
    int left = 0, right = i - 1;
    while (left <= right) {
      if ((long)arr[left] * arr[right] > arr[i])
        right--;
      else if ((long)arr[left] * arr[right] < arr[i])
        left++;
      else {
        if (left == right)
          dp[i] += (dp[left] * dp[right]);
        else
          dp[i] += 2 * (dp[left] * dp[right]);
        left++;
        right--;
      }
    }
    ans = ((ans % mod) + dp[i]) % mod;
  }
  return ans;
}

int main() {
  int a1[] = {2, 4}, a2[] = {2, 4, 5, 10};
  printf("%d\n", numFactoredBinaryTrees(a1, ARRAY_SIZE(a1))); // expect: 3
  printf("%d\n", numFactoredBinaryTrees(a2, ARRAY_SIZE(a2))); // expect: 7
}