🚀 100% || DP Solution Then Math || Explained Intuition 🚀
Problem Description\n\nGiven a positive integer n, the task is to break it into the sum of k positive integers, where k >= 2, in a way that maximizes their prod
# Problem Description\n\nGiven a positive integer `n`, the **task** is to break it into the sum of `k` positive integers, where $$k >= 2$$, in a way that **maximizes** their product. Return the **maximum** product achievable.\n\n- **Constraints:**\n    - `2 <= n <= 58`\n\nSeem tough? \uD83E\uDD14\n\n---\n\n\n\n# Intuition\nHi there\uD83D\uDE03\n\nLet\'s take a look on today\'s problem.\uD83D\uDC40\nSimply, the task is to find maximum product for the number that sum up to `n`.\nActually, My team encountered this problem in **EgyptianCPC** **2022** **Qualifications** \uD83D\uDE02 \n\nHow can we think about a solution for this problem?\uD83E\uDD14\n- We can notice two things: \uD83E\uDD29\n    - **First**, The **constraints** for the problem is not large its only `58`\n    - **Second**, The task is to **maximize** some product. \u2197\n\nInteresting, I think it seems a task for our hero **Dynamic Programming**.\uD83E\uDDB8\u200D\u2642\uFE0F\nYES, **Dynamic Programming** can be used to **maximum** the desired product for the input number.\nIt has two methods **Top-Down** & **Bottom-Up**.\n\nToday, I only implemented **Bottom-Up** since anyone of them is easy to be implemented once you understood the other.\n\nAlright, Let\'s talk about some **implementation** details for **DP**.\n- **Base Cases** for **maximum** product?\n    - if `n = 2` then maximum product is `1` which is `1 + 1`.\n    - if `n = 3` then maximum product is `2` which is `2 + 1`.\n\n- **Base Cases** for **DP table**?\n    - if `n = 1` then its entry is `1` since if the remaining in the sum is `1` then we will multiply by `1`.\n    - if `n = 2` then its entry is `2` since if the remaining in the sum is `2` then we will multiply by `2`.\n    - if `n = 3` then its entry is `3` since if the remaining in the sum is `3` then we will multiply by `3`.\n```\nEX: n = 5\nsum = 3 + 2 \nproduct = dp[3] * dp[2] = 6\n```\n\n- **Inner loop** for the DP solution ?\nAs we will see,  we will loop from `1` to `num / 2`. Why not from `1` to `num`?\nsince any number after `num / 2` will be **redundant**.\n```\nEX: n = 10\n10 = 6 + 4 = 4 + 6\n10 = 7 + 3 = 3 + 7\n```\n\n**OKKKKKK**\n\nAfter seeing the **DP** Solution can we do **better** ?\uD83E\uDD14\nActually **YES** !\uD83E\uDD2F\uD83E\uDD2F\uD83E\uDD2F\nLet\'s look an **observation** from the DP Solution \uD83D\uDC40\n\n![image.png](https://assets.leetcode.com/users/images/cb9362eb-bab0-4c2f-892a-2396aef1f8c5_1696556221.15878.png)\n\nThis list is what I **printed** in my **CLion IDE** after implementing the **DP** Solution for number `20`.\nCan we see some pattern ?\nYES, the answer is always **utilizing** the number `3` but how?\nIt tries to multiply with `3s` always with taking into **considration** the remainder.\nAlso, How? \uD83D\uDE02\n\n**Case1:** For remainder `0`, The sum is only **sum** of `3s` and product is **product** of these `threes`\n```\nEX: n = 9\nsum = 3 + 3 + 3\nproduct = 27\n```\n```\nEX: n = 15\nsum = 3 + 3 + 3 + 3 + 3\nproduct = 243\n```\n\n**Case2:** For remainder `1`, Since there is a remainder we want to utilize it. **not** by summing all the `3s` we can, but we can let one of these `3s` **away** and **replace** it with `4`.\n```\nEX: n = 10\nsum = 3 + 3 + 4\nproduct = 36\n```\n```\nEX: n = 16\nsum = 3 + 3 + 3 + 3 + 4\nproduct = 324\n```\n\n**Case3:** For remainder `2`, Simply we can seek for the all numbers of `3s` we can then **multiply** by the remaining `2`.\n```\nEX: n = 11\nsum = 3 + 3 + 3 + 2\nproduct = 54\n```\n```\nEX: n = 17\nsum = 3 + 3 + 3 + 3 + 3 + 2\nproduct = 486\n```\n\nAnd this is simply the **Math** solution. The interesting thing that to fully understand it you must **pass** by the **DP** solution since we are sure that **DP** will give you the **optimal** answer.\n\n\n\n## **EDIT**\nThanks to [@lixx2100](/lixx2100), He added very interesting proof in the discussions section.\n\nAssuming we will break **n** into **(n / x)** x\'s then the product will be **x^(n / x)** and this is what we want to **maximize**.\nLet\'s take it\'s **derivative** and equal it to **zero** to find the value of **x** that **maximize** the equation.\n\nThe **derivative** will be **n * x^(n/x-2) * (1 - ln(x))**.\nequatin **n * x^(n/x-2) * (1 - ln(x)) = 0**. will eventually make us end with **x = e** (Euler\'s Number).\nWhich means that the result of the equation **x^(n / x)** will **increase** until **x** reaches **e** and there will be its **maximum** after that it will begin to **decrease**.\n\nSeems nice till now! But we need **x** to be an integer ?\nsince we have **2 < e < 3** then we have to options to use **2** or **3**. but since **3** is the **closer** number to **e** then we will use it since it will give it **greater** value than **2**.\n\nand of course there will be **corner cases** we discussed above considering the **remainder** of the required number to be handeled.\n\n\n\n\nAnd this is the solution for our today\'S problem I hope that you understood it\uD83D\uDE80\uD83D\uDE80\n\n\n---\n\n\n\n\n# Proposed Approaches\n## DP\n1. **Base Cases:**\n   - If `n` is `2`, return `1`.\n   - If `n` is `3`, return `2`.\n2. **Create** a DP table (array) called `maxProduct` of size `n + 1` to store the `maximum` products for each number up to `n`.\n3. **Base Cases For the Table:**\n   - Set `maxProduct[1]` to 1.\n   - Set `maxProduct[2]` to 2.\n   - Set `maxProduct[3]` to 3.\n4. **DP Iteration:**\n   - Iterate from `4` to `n`.\n   - For each number `num` from `4` to `n`:\n     - Initialize a variable `maxProductForNum` to `0`.\n     - Iterate through smaller numbers from `1` to `num / 2`:\n       - Calculate the product of the **smaller** number and its **complement** (difference from `num`).\n       - Update `maxProductForNum` to be the **maximum** of the current value and the calculated product.\n     - Update `maxProduct[num]` with `maxProductForNum`.\n5. Return `maxProduct[n]` as the maximum product achievable for the given `n`.\n\n## Complexity\n- **Time complexity:** $$O(N^2)$$\nSince we are using **nested** for loops **one** is iterating from `4` to `n` and the **inner** for loop is iterating from `1` to `num / 2` then complexity is `N * N / 2` which is `O(N^2)`.\n- **Space complexity:** $$O(N)$$\nSince we are an array to store the **best** solution for all number up to `N` then complexity is `O(N)`.\n\n---\n## Math\n1. **Base Cases:**\n   - If `n` is less than 4, return `n - 1`.\n2. Calculate **Number of Threes** by Calculating the integer division of `n` by `3` and store it in `numOfThrees`.\n3. Calculate Initial Product by Initializing `productOfThrees` with the result of raising `3` to the power of `numOfThrees`.\n4. **Adjust Product Based on Remainder:**\n   - If `n` modulo `3` equals `1`:\n     - Update `productOfThrees` by **dividing** by `3` and then **multiplying** by `4`.\n   - Else if `n` modulo `3` equals `2`:\n     - Update `productOfThrees` by **multiplying** by `2`.\n5. Return the final value of `productOfThrees` as the **maximum** product achievable for the given `n`.\n\n## Complexity\n- **Time complexity:** $$O(log(N))$$\nSince we are calculating the power for the answer which is `O(log(N))` using **fast power algorithm** (I will put refrence for it in the comments).\n- **Space complexity:** $$O(1)$$\nSince we are only storing couple of constant variables.\n\n\n\n---\n\n\n\n# Code\n## DP\n```C++ []\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        // handle base cases\n        if (n == 2) return 1;\n        if (n == 3) return 2;\n\n        // Dynamic programming table to store maximum products\n        vector<int> maxProduct(n + 1, 0);\n\n        // Base cases for numbers 1, 2, and 3 -only for computing for rest of numbers-\n        maxProduct[1] = 1;\n        maxProduct[2] = 2;\n        maxProduct[3] = 3;\n\n        // Fill the dynamic programming table for larger numbers\n        for (int num = 4; num <= n; ++num) {\n            int maxProductForNum = 0;\n            // Iterate through smaller numbers to calculate the maximum product\n            for (int subNum = 1; subNum <= num / 2; ++subNum) {\n                maxProductForNum = max(maxProductForNum, maxProduct[subNum] * maxProduct[num - subNum]);\n            }\n            // Update the maximum product for the current number\n            maxProduct[num] = maxProductForNum;\n        }\n\n        return maxProduct[n];\n    }\n};\n```\n```Java []\nclass Solution {\n    public int integerBreak(int n) {\n        // Handle base cases\n        if (n == 2) return 1;\n        if (n == 3) return 2;\n\n        // Dynamic programming table to store maximum products\n        int[] maxProduct = new int[n + 1];\n\n        // Base cases for numbers 1, 2, and 3 -only for computing for the rest of the numbers-\n        maxProduct[1] = 1;\n        maxProduct[2] = 2;\n        maxProduct[3] = 3;\n\n        // Fill the dynamic programming table for larger numbers\n        for (int num = 4; num <= n; ++num) {\n            int maxProductForNum = 0;\n            // Iterate through smaller numbers to calculate the maximum product\n            for (int subNum = 1; subNum <= num / 2; ++subNum) {\n                maxProductForNum = Math.max(maxProductForNum, maxProduct[subNum] * maxProduct[num - subNum]);\n            }\n            // Update the maximum product for the current number\n            maxProduct[num] = maxProductForNum;\n        }\n\n        return maxProduct[n];\n    }\n}\n```\n```Python []\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        # Handle base cases\n        if n == 2:\n            return 1\n        if n == 3:\n            return 2\n\n        # Dynamic programming table to store maximum products\n        max_product = [0] * (n + 1)\n\n        # Base cases for numbers 1, 2, and 3 -only for computing for the rest of the numbers-\n        max_product[1] = 1\n        max_product[2] = 2\n        max_product[3] = 3\n\n        # Fill the dynamic programming table for larger numbers\n        for num in range(4, n + 1):\n            max_product_for_num = 0\n            # Iterate through smaller numbers to calculate the maximum product\n            for sub_num in range(1, num // 2 + 1):\n                max_product_for_num = max(max_product_for_num, max_product[sub_num] * max_product[num - sub_num])\n            # Update the maximum product for the current number\n            max_product[num] = max_product_for_num\n\n        return max_product[n]\n```\n\n\n---\n\n## Math\n\n```C++ []\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        // Base cases: for n < 4, return n-1\n        if (n < 4)\n            return n - 1;\n\n        // Calculate the number of times 3 can be multiplied\n        int numOfThrees = n / 3;\n\n        // Initialize the answer with the product of 3 raised to numOfThrees\n        long long productOfThrees = pow(3, numOfThrees);\n\n        // Adjust the product based on the remainder when divided by 3\n        if (n % 3 == 1) {\n            // If remainder is 1, you can multiply by 4 instead of 3\n            productOfThrees /= 3;\n            productOfThrees *= 4;\n        } else if (n % 3 == 2) {\n            // If remainder is 2, multiply by 2\n            productOfThrees *= 2;\n        }\n\n        // Return the maximum product\n        return productOfThrees;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public int integerBreak(int n) {\n        // Base cases: for n < 4, return n-1\n        if (n < 4)\n            return n - 1;\n\n        // Calculate the number of times 3 can be multiplied\n        int numOfThrees = n / 3;\n\n        // Initialize the answer with the product of 3 raised to numOfThrees\n        long productOfThrees = (long) Math.pow(3, numOfThrees);\n\n        // Adjust the product based on the remainder when divided by 3\n        if (n % 3 == 1) {\n            // If remainder is 1, you can multiply by 4 instead of 3\n            productOfThrees /= 3;\n            productOfThrees *= 4;\n        } else if (n % 3 == 2) {\n            // If remainder is 2, multiply by 2\n            productOfThrees *= 2;\n        }\n\n        // Return the maximum product\n        return (int) productOfThrees;\n    }\n}\n```\n```Python []\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        # Base cases: for n < 4, return n-1\n        if n < 4:\n            return n - 1\n\n        # Calculate the number of times 3 can be multiplied\n        num_of_threes = n // 3\n\n        # Initialize the answer with the product of 3 raised to num_of_threes\n        product_of_threes = 3 ** num_of_threes\n\n        # Adjust the product based on the remainder when divided by 3\n        if n % 3 == 1:\n            # If remainder is 1, you can multiply by 4 instead of 3\n            product_of_threes //= 3\n            product_of_threes *= 4\n        elif n % 3 == 2:\n            # If remainder is 2, multiply by 2\n            product_of_threes *= 2\n\n        # Return the maximum product\n        return product_of_threes\n```\n\n\n\n\n\n\n![leet_sol.jpg](https://assets.leetcode.com/users/images/5b9a7991-40c7-4d0c-9577-fe8eb85af1af_1696553242.1328564.jpeg)\n\n\n
['Math', 'Dynamic Programming', 'Python', 'C++', 'Java', 'Python3']