✅☑[C++/C/Java/Python/JavaScript]  || Beats 100% ||3 Approaches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approach\n(Also explained in the code)\n\n#### Approach 1: (Math)\n\n1. If n is less than or equal to 3, we return n - 
# *PLEASE UPVOTE IF IT HELPED*\n\n---\n\n\n# Approach\n***(Also explained in the code)***\n\n#### ***Approach 1: (Math)***\n\n1. If `n` is less than or equal to `3`, we return `n - 1` as the maximum product in this case.\n\n1. We calculate the remainder `rem` when `n` is divided by `3`, and we find the quotient `q` of this division.\n\n1. Depending on the value of `rem`, we compute the **maximum product**:\n\n    - If rem is `0`, it means `n` is a multiple of `3`, so we return `3^q`.\n    - If rem is `1`, we reduce `q` by `1` and return `3^(q-1) * 4`.\n    - If rem is `2`, we return `3^q * 2`.\n\n#### Complexity\n- **Time complexity:**\n$$O(1)$$\n\n- **Space complexity:**\n$$O(1)$$\n\n#### Code\n```C++ []\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        // If n is less than or equal to 3, return n-1 as this is the base case.\n        if (n <= 3) return n - 1;\n\n        // Find the remainder when n is divided by 3.\n        int rem = n % 3;\n\n        // Calculate the quotient when n is divided by 3.\n        int q = n / 3;\n\n        // Based on the remainder, calculate the result.\n        if (rem == 0) return pow(3, q);\n        else if (rem == 1) return pow(3, q - 1) * 4;\n        else if (rem == 2) return pow(3, q) * 2;\n\n        // This line should never be reached.\n        return 0;\n    }\n};\n\n```\n```C []\n#include <stdio.h>\n#include <math.h>\n\nint integerBreak(int n) {\n    // If n is less than or equal to 3, return n-1 as this is the base case.\n    if (n <= 3) return n - 1;\n\n    // Find the remainder when n is divided by 3.\n    int rem = n % 3;\n\n    // Calculate the quotient when n is divided by 3.\n    int q = n / 3;\n\n    // Based on the remainder, calculate the result.\n    if (rem == 0) return (int)pow(3, q);\n    else if (rem == 1) return (int)pow(3, q - 1) * 4;\n    else if (rem == 2) return (int)pow(3, q) * 2;\n\n    // This line should never be reached.\n    return 0;\n}\n\nint main() {\n    int n = 10;\n    int result = integerBreak(n);\n    printf("Result: %d\\n", result);\n    return 0;\n}\n\n```\n```Java []\nclass Solution {\n    public int integerBreak(int n) {\n        // If n is less than or equal to 3, return n-1 as this is the base case.\n        if (n <= 3) return n - 1;\n\n        // Find the remainder when n is divided by 3.\n        int rem = n % 3;\n\n        // Calculate the quotient when n is divided by 3.\n        int q = n / 3;\n\n        // Based on the remainder, calculate the result.\n        if (rem == 0) return (int)Math.pow(3, q);\n        else if (rem == 1) return (int)Math.pow(3, q - 1) * 4;\n        else if (rem == 2) return (int)Math.pow(3, q) * 2;\n\n        // This line should never be reached.\n        return 0;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        # If n is less than or equal to 3, return n-1 as this is the base case.\n        if n <= 3:\n            return n - 1\n\n        # Find the remainder when n is divided by 3.\n        rem = n % 3\n\n        # Calculate the quotient when n is divided by 3.\n        q = n // 3\n\n        # Based on the remainder, calculate the result.\n        if rem == 0:\n            return 3 ** q\n        elif rem == 1:\n            return 3 ** (q - 1) * 4\n        elif rem == 2:\n            return 3 ** q * 2\n\n        # This line should never be reached.\n        return 0\n\n```\n```Javascript []\nclass Solution {\n    integerBreak(n) {\n        // If n is less than or equal to 3, return n-1 as this is the base case.\n        if (n <= 3) return n - 1;\n\n        // Find the remainder when n is divided by 3.\n        let rem = n % 3;\n\n        // Calculate the quotient when n is divided by 3.\n        let q = Math.floor(n / 3);\n\n        // Based on the remainder, calculate the result.\n        if (rem === 0) return Math.pow(3, q);\n        else if (rem === 1) return Math.pow(3, q - 1) * 4;\n        else if (rem === 2) return Math.pow(3, q) * 2;\n\n        // This line should never be reached.\n        return 0;\n    }\n}\n\nconst solution = new Solution();\nconsole.log(solution.integerBreak(10)); // Example usage\n\n```\n\n---\n#### ***Approach 2: (Greedy Method)***\n\n1. If `n` is 2 or 3, the optimal way is to break it into two or three equal parts. So, the function returns `n - 1` as the result.\n\n1. Initialize a variable `result` to keep track of the product of the breaking numbers.\n\n1. Use a `while` loop to iteratively break down `n` into as many 3\'s as possible. Each time, multiply the `result` by 3 and subtract 3 from `n`. This step ensures that we break `n` into as many equal parts of 3 as possible, which tends to maximize the product.\n\n1. After the loop, there are three possibilities for `n`:\n\n    - If `n` is 4, we can break it into two equal parts (2 * 2), so we multiply the `result` by 4.\n    - If `n` is greater than 4, we have a remainder that is less than  Multiply the `result` by this remainder.\n1. Return the `result` as the maximum product achievable by breaking `n` into integers.\n\n#### Complexity\n- **Time complexity:**\n$$O(n)$$\n\n- **Space complexity:**\n$$O(1)$$\n\n#### Code\n```C++ []\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        // If n is less than or equal to 3, return n-1 as this is the base case.\n        if (n <= 3) {\n            return n - 1;\n        }\n        \n        int result = 1;\n        \n        // Repeatedly subtract 3 from n and multiply the result by 3 until n becomes less than or equal to 4.\n        while (n > 4) {\n            result *= 3;\n            n -= 3;\n        }\n        \n        // Multiply the remaining value of n to the result.\n        result *= n;\n        \n        return result;\n    }\n};\n\n\n```\n```C []\n#include <stdio.h>\n\nint integerBreak(int n) {\n    // If n is less than or equal to 3, return n-1 as this is the base case.\n    if (n <= 3) {\n        return n - 1;\n    }\n    \n    int result = 1;\n    \n    // Repeatedly subtract 3 from n and multiply the result by 3 until n becomes less than or equal to 4.\n    while (n > 4) {\n        result *= 3;\n        n -= 3;\n    }\n    \n    // Multiply the remaining value of n to the result.\n    result *= n;\n    \n    return result;\n}\n\nint main() {\n    int n = 10;\n    int result = integerBreak(n);\n    printf("Result: %d\\n", result);\n    return 0;\n}\n\n\n```\n```Java []\n\nclass Solution {\n    public int integerBreak(int n) {\n        // If n is less than or equal to 3, return n-1 as this is the base case.\n        if (n <= 3) {\n            return n - 1;\n        }\n        \n        int result = 1;\n        \n        // Repeatedly subtract 3 from n and multiply the result by 3 until n becomes less than or equal to 4.\n        while (n > 4) {\n            result *= 3;\n            n -= 3;\n        }\n        \n        // Multiply the remaining value of n to the result.\n        result *= n;\n        \n        return result;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        # If n is less than or equal to 3, return n-1 as this is the base case.\n        if n <= 3:\n            return n - 1\n        \n        result = 1\n        \n        # Repeatedly subtract 3 from n and multiply the result by 3 until n becomes less than or equal to 4.\n        while n > 4:\n            result *= 3\n            n -= 3\n        \n        # Multiply the remaining value of n to the result.\n        result *= n\n        \n        return result\n\n\n```\n```Javascript []\n\nclass Solution {\n    integerBreak(n) {\n        // If n is less than or equal to 3, return n-1 as this is the base case.\n        if (n <= 3) {\n            return n - 1;\n        }\n        \n        let result = 1;\n        \n        // Repeatedly subtract 3 from n and multiply the result by 3 until n becomes less than or equal to 4.\n        while (n > 4) {\n            result *= 3;\n            n -= 3;\n        }\n        \n        // Multiply the remaining value of n to the result.\n        result *= n;\n        \n        return result;\n    }\n}\n\nconst solution = new Solution();\nconsole.log(solution.integerBreak(10)); // Example usage\n\n\n```\n\n---\n\n#### ***Approach 3: (Dynamic Programming)***\n\n1. If `n` is less than or equal to 3, we return `n - 1` as this is the base case.\n\n1. We create a dynamic programming array `dp` to store the maximum product for integers from 2 to `n`.\n\n1. We initialize `dp[2]` and `dp[3]` as the base cases, representing the maximum products for 2 and 3.\n\n1. Using a loop, we fill the `dp` array for integers from 4 to `n` by considering two possibilities for breaking the integer and calculating the maximum product.\n\n1. The final result is stored in `dp[n]`, which represents the maximum product for the given integer `n`.\n\n#### Complexity\n- **Time complexity:**\n$$O(n)$$\n\n- **Space complexity:**\n$$O(n)$$\n\n#### Code\n```C++ []\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        // Base case: if n is less than or equal to 3, return n - 1\n        if (n <= 3) {\n            return n - 1;\n        }\n\n        // Create a dynamic programming array to store the maximum product for each integer from 2 to n.\n        vector<int> dp(n + 1);\n        dp[2] = 2; // Base case: maximum product for 2 is 2.\n        dp[3] = 3; // Base case: maximum product for 3 is 3.\n\n        // Fill the dp array for integers from 4 to n.\n        for (int i = 4; i <= n; ++i) {\n            // Calculate the maximum product by considering two possibilities:\n            // 1. Break i into i-2 and 2, and multiply dp[i-2] by 2.\n            // 2. Break i into i-3 and 3, and multiply dp[i-3] by 3.\n            dp[i] = max(dp[i - 2] * 2, dp[i - 3] * 3);\n        }\n\n        // The result is stored in dp[n].\n        return dp[n];\n    }\n};\n\n\n```\n```C []\n\n#include <stdio.h>\n\nint integerBreak(int n) {\n    if (n <= 3) {\n        return n - 1;\n    }\n\n    int dp[n + 1];\n    dp[2] = 2;\n    dp[3] = 3;\n\n    for (int i = 4; i <= n; ++i) {\n        dp[i] = (dp[i - 2] * 2) > (dp[i - 3] * 3) ? (dp[i - 2] * 2) : (dp[i - 3] * 3);\n    }\n\n    return dp[n];\n}\n\nint main() {\n    int n = 10; // Example input\n    printf("Maximum product: %d\\n", integerBreak(n));\n    return 0;\n}\n\n```\n```Java []\nclass Solution {\n    public int integerBreak(int n) {\n        if (n <= 3) {\n            return n - 1;\n        }\n\n        int[] dp = new int[n + 1];\n        dp[2] = 2;\n        dp[3] = 3;\n\n        for (int i = 4; i <= n; ++i) {\n            dp[i] = Math.max(dp[i - 2] * 2, dp[i - 3] * 3);\n        }\n\n        return dp[n];\n    }\n}\n\n\n```\n```python []\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n <= 3:\n            return n - 1\n\n        dp = [0] * (n + 1)\n        dp[2] = 2\n        dp[3] = 3\n\n        for i in range(4, n + 1):\n            dp[i] = max(dp[i - 2] * 2, dp[i - 3] * 3)\n\n        return dp[n]\n\n\n```\n```Javascript []\nfunction integerBreak(n) {\n    if (n <= 3) {\n        return n - 1;\n    }\n\n    const dp = new Array(n + 1).fill(0);\n    dp[2] = 2;\n    dp[3] = 3;\n\n    for (let i = 4; i <= n; ++i) {\n        dp[i] = Math.max(dp[i - 2] * 2, dp[i - 3] * 3);\n    }\n\n    return dp[n];\n}\n\n// Example usage:\nconst n = 10;\nconsole.log("Maximum product:", integerBreak(n));\n\n```\n\n# *PLEASE UPVOTE IF IT HELPED*\n\n---
['Math', 'Dynamic Programming', 'C', 'Python', 'C++', 'Java', 'JavaScript']