Java | Fastest | Beats 100% Time | Simple Math | Easy To Understand | Explanation
\n\n# Youtube Video:\nhttps://youtu.be/U0HHj3Y6ims\n\n---\n## Intuition\n\nTo maximize the product of the integers, we should try to break the number into as ma
![Screenshot 2023-10-06 075213.png](https://assets.leetcode.com/users/images/ab7418d5-e0cb-46e6-aa82-6b514dc40d45_1696559335.3639252.png)\n\n# Youtube Video:\n[https://youtu.be/U0HHj3Y6ims]()\n\n---\n## Intuition\n\nTo maximize the product of the integers, we should try to break the number into as many threes as possible. This is because multiplying multiple 3s gives a larger product compared to other combinations.\n\n## Approach\n\n1. We can handle specific cases where `n` is 2 or 3 since the product of 1s is better in these cases.\n\n2. Initialize a `product` variable to 1.\n\n3. While `n` is greater than 4, do the following:\n   - Multiply `product` by 3.\n   - Subtract 3 from `n`.\n\n4. Multiply the remaining `n` by `product`.\n\n5. Return the `product`.\n\n## Time Complexity\n\nThe time complexity is O(log n) because we reduce `n` by 3 in each iteration.\n\n## Space Complexity\n\nThe space complexity is O(1) since we use a constant amount of extra space.\n\n---\n**Example**: Let\'s take the number 10 and explore three different ways of breaking it down into positive integers:\n\n**1. Breaking into 1s**: In this case, we break 10 into 10 units of 1.\n\n   - 10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1\n   - Product = 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 = 1\n\n**2. Breaking into 2s and 1s**: In this case, we break 10 into 5 units of 2 and 1 unit of 1.\n\n   - 10 = 2 + 2 + 2 + 2 + 2 \n   - Product = 2 * 2 * 2 * 2 * 2 * 1 = 32\n\n**3. Breaking into 3s and 1s**: In this case, we break 10 into 3 units of 3 and 1 unit of 1.\n\n   - 10 = 3 + 3 + 4 + 1\n   - Product = 3 * 3 * 3 * 4 = 36\n\nAs you can see, breaking the number 10 into 3s and 1s results in the largest product (36). This demonstrates that multiplying multiple 3s together gives us a larger product compared to other combinations, such as breaking the number into 1s or 2s.\n\nThis is why the code in the solution tries to maximize the product by breaking `n` into as many threes as possible because it results in a larger product when compared to other combinations.\n\n---\n\n# Code\n```\nclass Solution {\n    public int integerBreak(int n) {\n        if(n==2)\n            return 1;\n        if(n==3)\n            return 2;\n        int prod =1;\n        while(n>4)\n        {\n            prod*=3;\n            n-=3;\n        }\n        prod*=n;\n        return prod;\n        \n    }\n}\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/5eff19f7-b040-4348-b1c8-da78eec7e573_1696559353.9797127.png)\n
['Math', 'Java']