【Video】Give me 10 minutes - How we think about a solution - Python, JavaScript, Java, C++
Intuition\nUse Dynamic Programming\n\n---\n\n# Solution Video\n\nhttps://youtu.be/LrnKFjcjsqo\n\n\u25A0 Timeline of video\n0:04 Understand question exactly and 
# Intuition\nUse Dynamic Programming\n\n---\n\n# Solution Video\n\nhttps://youtu.be/LrnKFjcjsqo\n\n\u25A0 Timeline of video\n`0:04` Understand question exactly and approach to solve this question\n`1:33` How can you calculate number of subtrees?\n`4:12` Demonstrate how it works\n`8:40` Coding\n`11:32` Time Complexity and Space Complexity\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,831\nMy initial goal is 10,000\nThank you for your support!\n\n---\n\n# Approach\n\n## How we think about a solution\n\nFirst of all, Let\'s understand question exactly.\n\n```\ninput: [2,3,4]\n```\nWhen input is `[2,3,4]`, we can create a binary tree. This is one of examples.\n```\n   24\n  /  \\\n 2    12\n      / \\\n     3   4\n\nEach number may be used for any number of times.\n24 comes from 2 * 12\n2 comes from 2\n12 comes from 3 * 4\n3 comes from 3\n4 comes from 4\n```\n\nAll we have to do is to count this kind of tree we can make with input array. But difficulty is we don\'t know we will have `24` or `12` in the end. Do you calculate them one by one?\n\nActually, you don\'t have to calculate them exactly. Then how do we calculate them? We can take another approach.\n\n---\n\n\u2B50\uFE0F Points\n\nWe need to calculate number of subtree when each input number is root. \n\nLet\'s say we have 3 subtrees for some root number and 5 subtrees for the other root number. In that case, total number of trees are 8. Because each number may be used for any number of times, we can use any number for root or children.\n\n---\n\n- How can you calculate number of subtrees?\n\nWe have to multiply both sides of children for each non-leaf node. At least we can say\n\n---\n\n\u2B50\uFE0F Points\n\nThe number of the root must be a multiple of the current number. For example, root is `10`, current left child number is `5`. In that case there is possibiilty that we can create one of subtrees.\n\nWe can check it easily with 0 remainder.\n\n```[]\nif root % factor == 0\n```\n\n---\n\nBut we have one more important thing. Root is `10` and current left child number is `5`. In that case, what number do we need for right child number? Easy right? It\'s `2`\n\nSo, if we have node of value `2`, we can create at least one of subtrees.\n\n---\n\n\u2B50\uFE0F Points\n\nWe need to check if we have a number we need right now. Simply you can calculate it by division.\n\n```[]\nroot // factor\n```\n\nin the end,\n\n**number of subtree of the root = subtree of left side * subtree of right side**\n\nroot 10 = number of subtree of 5 * number of subtree of 2 + 1\n\n- Why +1?\n\nThat\'s because we can definitely create subtree of only 10. so in real solution code, we initialize each number of subtree with 1, so we don\'t write `+1` in solution code. \n\n---\n\n\nFrom the above idea, we need to keep previous numbers for future numbers, so seems like we can use Dynamic Programming.\n\n## How it works\n\nLet\'s think about this case again.\n\n```\ninput: [2,3,4]\n```\n\nWhen `2` is root. the rest of numbers are bigger than `2`. so we can create only `[2]`. subtree below is `HashMap`.\n\n```\nsubtree = {2: 1}\n\nkey: root number\nvalue: number of subtrees\n```\n\nHow about root is `3`. `2` and `4` doesn\'t meet this codition.\n\n```\nif root(3) % factor(2 or 4) == 0\n```\nSo, we will have only `[3]`.\n```\nsubtree = {2: 1, 3: 1}\n```\n\nHow about root is `4`. `2` meet the codition above, because we can create \n\n```\n   4\n  /  \\\n 2    2\n\nof course we can create subtree of only 4\n```\n\nDo you remember this point?\n\n---\n\n\u2B50\uFE0F Points\n\nnumber of subtree of the root = subtree of left side * subtree of right side\n\n---\n\nSo,\n\n```[]\nsubtree[root] += subtree[factor] * subtree[root // factor]\n\u2193\nsubtree[4] += subtree[2](=1) * subtree[4 // 2](=1)\n\u2193\nsubtree[4] = 2 \n\nall number of subtrees are initilized with 1,\nbacause of subtree of only root itself. We can definitely create it.\nIn this case, 1 + 1 = 2\n\n```\n\n```\nsubtree = {2: 1, 3: 1, 4: 2}\n```\n```\nOutput: 4 (1 + 1 + 2)\n```\n\n\n---\n\n\n\n## Visualization to understand easily and deeply\n\nTo understand easily and deeply. Let me explain this.\n```[]\nsubtree[4] += subtree[2](=1) * subtree[4 // 2](=1)\n```\n![IMG_6618.JPG](https://assets.leetcode.com/users/images/64519aab-0b3c-4d0a-95b6-754d513263d8_1698307985.7692955.jpeg)\n\n My shadow... lol\n\nWhen root is `4`, the `4` has two `2` nodes on the left and right side. In that case, Look at each triangle that has root 2 on left and right side.\n\n```\nsubtree = {2: 1, 3: 1}\n```\n\nWe know that if we have root 2 node, we can create only 1 subtree when input array is `[2,3,4]`(Look at `HashMap` above), so in the triangle parts, we can create 1 subtree from left triangle and 1 subtree from right triangle. That\'s why combination of the left side and right side should be `1 * 1 = 1`. Then add `+1` for the case where subtree of only root 4 itself.\n\nIn the end `1 + 1 = 2`.\n\nIf we have 2 subtrees on the right side. we can create 1 * 2 combinations.\n```\nleft side\nsubtree A\n\nright side\nsubtree B\nsubtree C\n\nall combinations of left and right should be AB and AC (= 1 * 2)\n```\nIf we have 2 subtrees on the left and right side. we can create 2 * 2 combinations.\n```\nleft side\nsubtree A\nsubtree D\n\nright side\nsubtree B\nsubtree C\n\nall combinations of left and right should be \nAB, AC, DB, DC (= 2 * 2)\n\n```\n\nEasy\uD83D\uDE06\n\n\nThis idea comes from a solution for unique binary search tree problem. I have a video. I took it last year.\n\nhttps://youtu.be/bTEcK_dh9QM\n\nI hope you understand main idea.\nLet\'s see real algorithm!\n\nI\'m rushed a little bit because I have a school event for my kids today. If I mistake something, let me know. Thank you!\n\n##### Algorithm Overview:\nThe algorithm aims to calculate the number of binary trees that can be formed using the elements in the input list `arr`, considering each element as a potential root. The result should be returned modulo `10^9 + 7`.\n\n##### Detailed Explanation:\n1. Sort the input list `arr` in ascending order.\n   - This ensures that elements are processed in ascending order, which is crucial for the dynamic programming approach used.\n\n2. Initialize an empty dictionary called `subtree` to keep track of the number of binary trees that can be formed with each element as the root.\n   - The keys of this dictionary will be the elements in `arr`, and the values will represent the number of binary trees that can be formed with the respective element as the root.\n\n3. Iterate through the sorted elements in `arr` with the variable `root`:\n   a. Initialize the `subtree` count for the current `root` to 1.\n      - This accounts for the possibility that the current element itself can be a single-node binary tree.\n\n4. Nested loop: Iterate through the elements in `arr` with the variable `factor`. This loop checks each element as a potential child node for the current `root`:\n   a. If `factor` is greater than or equal to the current `root`, exit the loop.\n      - This is because factors should be smaller than the root.\n   b. Check if the current `root` is divisible by `factor` (i.e., `root % factor == 0`) and if the result of the division (`root // factor`) is already present in the `subtree` dictionary.\n      - If both conditions are met, it means `factor` can be a child node of the current `root`.\n\n5. If the conditions in step 4 are met, update the `subtree` count for the current `root`:\n   a. Increment the `subtree` count for the current `root` by multiplying the `subtree` count of the `factor` by the `subtree` count of the division result (`root // factor`).\n      - This update accounts for the number of binary trees that can be formed with the current `root`.\n\n6. After processing all elements in the nested loop, you have calculated the number of binary trees that can be formed with the current `root` as the root node.\n\n7. The outer loop continues to the next `root` element, and the process repeats.\n\n8. Once all elements in `arr` have been processed, the `subtree` dictionary contains the number of binary trees that can be formed with each element as the root.\n\n9. Calculate the `total_trees` by summing up the values in the `subtree` dictionary.\n\n10. Finally, return `total_trees` modulo `(10^9 + 7)` to ensure the result is within the specified range.\n\nIn summary, this code iterates through the elements of `arr` while keeping track of the number of binary trees that can be formed with each element as the root node, taking advantage of previously calculated values for smaller factors.\n\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\nSorting the arr list takes $$O(n log n)$$ time, where "n" is the number of elements in the list.\n\nThe two nested loops iterate through the elements in arr. In the worst case, both loops will iterate over all elements. Therefore, the time complexity of this part is $$O(n^2)$$.\n\n\n- Space complexity: $$O(n)$$\n\nThe subtree dictionary stores values for each element in arr, so it has a space complexity of $$O(n)$$ to store the results for each element.\n\nThe other variables used in the code, such as root, factor, and total_trees, have constant space complexity and do not depend on the input size.\n\n```python []\nclass Solution:\n    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n        arr.sort()\n        subtree = {}\n\n        for root in arr:\n            subtree[root] = 1\n\n            for factor in arr:\n                if factor >= root:\n                    break\n            \n                if root % factor == 0 and root // factor in subtree:\n                    subtree[root] += subtree[factor] * subtree[root // factor]\n\n        total_trees = sum(subtree.values())\n        return total_trees % (10**9 + 7)       \n```\n```javascript []\n/**\n * @param {number[]} arr\n * @return {number}\n */\nvar numFactoredBinaryTrees = function(arr) {\n    arr.sort((a, b) => a - b);\n    const subtreeCount = {};\n\n    for (const root of arr) {\n        subtreeCount[root] = 1;\n\n        for (const factor of arr) {\n            if (factor >= root) {\n                break;\n            }\n\n            if (root % factor === 0 && subtreeCount[root / factor]) {\n                subtreeCount[root] += subtreeCount[factor] * subtreeCount[root / factor];\n            }\n        }\n    }\n\n    let totalTrees = 0;\n    for (const key in subtreeCount) {\n        totalTrees += subtreeCount[key];\n    }\n\n    return totalTrees % (10 ** 9 + 7);    \n};\n```\n```java []\nclass Solution {\n    public int numFactoredBinaryTrees(int[] arr) {\n        Arrays.sort(arr);\n        Map<Integer, Long> subtreeCount = new HashMap<>();\n\n        for (int root : arr) {\n            subtreeCount.put(root, 1L);\n\n            for (int factor : arr) {\n                if (factor >= root) {\n                    break;\n                }\n\n                if (root % factor == 0 && subtreeCount.containsKey(root / factor)) {\n                    subtreeCount.put(root, (subtreeCount.get(root) + subtreeCount.get(factor) * subtreeCount.get(root / factor)));\n                }\n            }\n        }\n\n        long totalTrees = 0L;\n        for (int key : subtreeCount.keySet()) {\n            totalTrees = (totalTrees + subtreeCount.get(key)) % 1_000_000_007;\n        }\n\n        return (int) totalTrees;       \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        sort(arr.begin(), arr.end());\n        unordered_map<long, long> subtreeCount;\n\n        for (long root : arr) {\n            subtreeCount[root] = 1;\n\n            for (long factor : arr) {\n                if (factor >= root) {\n                    break;\n                }\n\n                if (root % factor == 0 && subtreeCount.find(root / factor) != subtreeCount.end()) {\n                    subtreeCount[root] += subtreeCount[factor] * subtreeCount[root / factor];\n                }\n            }\n        }\n\n        long totalTrees = 0;\n        for (const auto& entry : subtreeCount) {\n            totalTrees += entry.second;\n        }\n\n        return totalTrees % static_cast<int>(pow(10, 9) + 7);        \n    }\n};\n```\n\n- Why do we sort input array?\n\nSorting the `arr` is done to comply with the constraints specified in the problem. The given constraint is that "each integer arr[i] is strictly greater than 1," which means that there are no integers in `arr` that are less than or equal to 1, and all integers are greater than or equal to 2.\n\nTo satisfy this condition, the array is sorted. Sorting the array ensures that the elements are processed in ascending order, from smaller integers to larger ones, which is essential for the effective application of the dynamic programming algorithm.\n\nBy sorting the array, you can solve the problem more efficiently, and it allows you to apply dynamic programming recursively, starting with smaller numbers and gradually progressing to larger numbers. This enables an efficient way to find the solution to the problem.\n\n\n---\n\n\n\nIf you are not familar with Dynamic Programming. This video might help you to understand it!\n\nhttps://youtu.be/MUU6tgywdPY\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/k-th-symbol-in-grammar/solutions/4205721/video-give-me-8-minutes-how-we-think-about-solution-python-javascript-java-c/\n\nvideo\nhttps://youtu.be/cCN38sMai-c\n\n\u25A0 Timeline of the video\n`0:04` Important Rules\n`0:17` How can you find the answer\n`1:13` How can you find the parent of the target pair\n`3:05` How can you know 0 or 1 in the target pair\n`3:40` How can you calculate the first position and the second position in the target pair\n`5:34` Coding\n`7:56` Time Complexity and Space Complexity\n\n\n
['C++', 'Java', 'Python3', 'JavaScript']