funcnumFactoredBinaryTrees(arr []int)int { sort.Ints(arr) dp := make([]int64, len(arr)) res, mod := int64(0), int64(1e9 + 7) for i := 0; i < len(arr); i++ { dp[i] = 1 for left, right := 0, i - 1; left <= right; left++ { for left <= right && int64(arr[left]) * int64(arr[right]) > int64(arr[i]) { right-- } if left <= right && int64(arr[left]) * int64(arr[right]) == int64(arr[i]) { if left == right { dp[i] = (dp[i] + dp[left] * dp[right]) % mod } else { dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod } } } res = (res + dp[i]) % mod } returnint(res) }
intnumFactoredBinaryTrees(int *arr, int arrSize){ qsort(arr, arrSize, sizeof(int), cmp); longlong *dp = (longlong *)malloc(arrSize * sizeof(longlong)); longlong res = 0, mod = 1e9 + 7; for (int i = 0; i < arrSize; i++) { dp[i] = 1; for (int left = 0, right = i - 1; left <= right; left++) { while (left <= right && (longlong)arr[left] * arr[right] > arr[i]) { right--; } if (left <= right && (longlong)arr[left] * arr[right] == arr[i]) { if (left == right) { dp[i] = (dp[i] + dp[left] * dp[right]) % mod; } else { dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod; } } } res = (res + dp[i]) % mod; } return res; }
[sol1-Python3]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution: defnumFactoredBinaryTrees(self, arr: List[int]) -> int: n = len(arr) arr = sorted(arr) dp = [1] * n res, mod = 0, 10**9 + 7 for i inrange(n): left, right = 0, i - 1 while left <= right: while right >= left and arr[left] * arr[right] > arr[i]: right -= 1 if right >= left and arr[left] * arr[right] == arr[i]: if right != left: dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod else: dp[i] = (dp[i] + dp[left] * dp[right]) % mod left += 1 res = (res + dp[i]) % mod return res