Time&Space Complexity O(1); Math solution: 96.58% Time/ 67.94% Space
Intuition\n Describe your first thoughts on how to solve this problem. \nSimply speaking it is a math problem instead of DP Problem. If the number is greater th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSimply speaking it is a math problem instead of DP Problem. If the number is greater than 3, we need to break the number into summation of 2 and 3. This leads to the largest product.\n\nWe need as many 3 as possible because 3^2 is greater than 2^3.\n\nHowever, special case for 4, 2$\\times$2 > 3 $\\times$ 1.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIf n = 2 we break it into 1+1 = 2\nIf n = 3 we break it into 1+2 = 3 \nIf n >= 4:\n----If n%3==0: break n into 3 + 3 + 3 + ... + 3\n----If n%3==1: break n into 3 + ... + 3 + 2 + 2: Number of 3 equals to n//3 - 1\n----If n%3==2: break n into 3 + ... + 3 + 2: Number of 3 equals to n//3\n# Complexity\n- Time complexity: O(1)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n <= 3:\n            return n - 1\n        elif n%3 == 0:\n            return 3**(int(n/3))\n        elif n%3 == 1:\n            return 3**(int(n/3)-1)*4\n        else:\n            return 3**(int(n/3))*2\n```\n\n# One Liner Code\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:    \n        return n-1 if n <= 3 else 3**(int(n/3)-1)*round(0.5*(n%3)**2 + 0.5*(n%3) + 3)\n```
['Math', 'Python3']