diff options
author | jack <0x6A73@pm.me> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <0x6A73@pm.me> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /binary_tree_factors.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'binary_tree_factors.c')
-rw-r--r-- | binary_tree_factors.c | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/binary_tree_factors.c b/binary_tree_factors.c new file mode 100644 index 0000000..378d283 --- /dev/null +++ b/binary_tree_factors.c @@ -0,0 +1,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 +} |