aboutsummaryrefslogtreecommitdiff
path: root/other/binary_tree_factors.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/binary_tree_factors.cpp')
-rw-r--r--other/binary_tree_factors.cpp31
1 files changed, 31 insertions, 0 deletions
diff --git a/other/binary_tree_factors.cpp b/other/binary_tree_factors.cpp
new file mode 100644
index 0000000..fef1b69
--- /dev/null
+++ b/other/binary_tree_factors.cpp
@@ -0,0 +1,31 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int numFactoredBinaryTrees(vector<int> &arr) {
+ sort(arr.begin(), arr.end());
+ int n = arr.size();
+ long ans = 0;
+ unordered_map<int, long> um;
+ for (int num : arr) {
+ long ways = 1;
+ double lim = sqrt(num);
+ for (int i = 0, fA = arr[0]; fA <= lim; fA = arr[++i]) {
+ if (num % fA != 0)
+ continue;
+ int fB = num / fA;
+ if (um.find(fB) != um.end())
+ ways += um[fA] * um[fB] * (fA == fB ? 1 : 2);
+ }
+ um[num] = ways;
+ ans = (ans + ways) % 1000000007;
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> arr = {2, 4};
+ cout << obj.numFactoredBinaryTrees(arr);
+}