leetcode

commit 7ea2dcb4b0e9d46039aaa23138730fcf27725718
parent fe2481131cfc2635ad0691aa7eb45423f89b979c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 26 Oct 2023 22:25:57 +0000

Daily Problem

Diffstat:
A
Problems/0823.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/0823.cpp b/Problems/0823.cpp
@@ -0,0 +1,38 @@
+class Solution {
+    static const int MOD = 1E9 + 7;
+
+    static int binary_search(const vector<int> &arr, const int end, const int target) {
+        int low = 0, high = end - 1;
+        while (low <= high) {
+            const int mid = low + (high - low) / 2;
+            if (arr[mid] == target) return mid;
+            if (arr[mid] > target)
+                high = mid - 1;
+            else
+                low = mid + 1;
+        }
+        return -1;
+    }
+
+  public:
+    int numFactoredBinaryTrees(vector<int> &arr) const {
+        static int mem[1000];
+        memset(mem, 0x00, sizeof(mem));
+
+        sort(begin(arr), end(arr));
+        long long res = 0;
+        for (int i = 0; i < arr.size(); i++) {
+            const int crnt = arr[i];
+            long long local = 1;
+            for (int j = 0; j < i; j++) {
+                if (crnt % arr[j] != 0) continue;
+                const int idx = binary_search(arr, i, crnt / arr[j]);
+                if (idx == -1) continue;
+                local = (local + (long long)mem[j] * mem[idx]) % MOD;
+            }
+            mem[i] = local;
+            res = (res + mem[i]) % MOD;
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -412,6 +412,7 @@ for solving problems.
 |  0814  |   Medium   | [Binary Tree Pruning](Problems/0814.cpp)                                                           |
 |  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                    |
 |  0820  |   Medium   | [Short Encoding of Words](Problems/0820.cpp)                                                       |
+|  0823  |   Medium   | [Binary Trees With Factors](Problems/0823.cpp)                                                     |
 |  0830  |   Medium   | [Kth Smallest Element in a BST](Problems/0230.cpp)                                                 |
 |  0835  |   Medium   | [Image Overlap](Problems/0835.cpp)                                                                 |
 |  0837  |   Medium   | [New 21 Game](Problems/0837.cpp)                                                                   |