Python O(1) one line solution - detailed explanation
Let\'s first consider the limiting behaviour of the solution. \n\nFor large n, our "integer break" will consist of splitting up n into b groups of x. So n = bx,
Let\'s first consider the limiting behaviour of the solution. \n\nFor large n, our "integer break" will consist of splitting up n into b groups of x. So n = bx, where rearranging yields b = <sup>n</sup>&frasl;<sub>x</sub>.\n\nOur goal is to maximize the product of these fragments, so we want to maximize f(x) = x<sup><sup>n</sup>&frasl;<sub>x</sub></sup>.\n\nUsing implicit differentiation, we find f\'(x) = nx<sup><sup>n</sup>&frasl;<sub>x</sub> - 2 </sup>(1 - *log*x). Setting f\'(x) = 0 gives x = **e**, so our objective function **f(x) is maximized at x = e**.\n\nObviously, **e** is not an integer, so we cannot split n into groups of **e** for the purposes of this question. However, this result gives us the intuition that n should be split into 2\'s and 3\'s, wherever possible, since 2 < **e** < 3.\n\nWe begin by working through the first several cases of n and try to identify a pattern: \n\n<table>\n<th> n </th>\n<th> Maximum Product </th>\n<th> # of 2\'s </th>\n<th> # of 3\'s </th>\n<tr>\n<td> 2 </td>\n<td> 1 x 1 = 1 </td>\n<td> 0 </td>\n<td> 0 </td>\n<tr>\n<td> 3 </td>\n<td> 1 x 2 = 2</td>\n<td> 1 </td>\n<td> 0 </td>\n<tr>\n<td> 4 </td>\n<td> 2 x 2 = 4</td>\n<td> 2 </td>\n<td> 0 </td>\n<tr>\n<td> 5 </td>\n<td> 2 x 3 = 6</td>\n<td> 1 </td>\n<td> 1 </td>\n<tr>\n<td> 6 </td>\n<td> 3 x 3 = 9</td>\n<td> 0 </td>\n<td> 2 </td>\n<tr>\n<td> 7 </td>\n<td> 2 x 2 x 3 = 12</td>\n<td> 2 </td>\n<td> 1 </td>\n<tr>\n<td> 8 </td>\n<td> 2 x 3 x 3 = 18</td>\n<td> 1 </td>\n<td> 2 </td>\n<tr>\n<td> 9 </td>\n<td> 3 x 3 x 3 = 27</td>\n<td> 0 </td>\n<td> 3 </td>\n<tr>\n<td> 10 </td>\n<td> 2 x 2 x 3 x 3 = 36</td>\n<td> 2 </td>\n<td> 2 </td>\n<tr>\n<td> 11 </td>\n<td> 2 x 3 x 3 x 3 = 54</td>\n<td> 1 </td>\n<td> 3 </td>\n<tr>\n<td> 12 </td>\n<td> 3 x 3 x 3 x 3 = 81</td>\n<td> 0 </td>\n<td> 4 </td>\n<tr>\n<td> 13 </td>\n<td> 2 x 2 x 3 x 3 x 3 = 108</td>\n<td> 2 </td>\n<td> 3 </td>\n<tr>\n<td> 14 </td>\n<td> 2 x 3 x 3 x 3 x 3 = 162</td>\n<td> 1 </td>\n<td> 4 </td>\n<tr>\n<td> 15 </td>\n<td> 3 x 3 x 3 x 3 x 3 = 243</td>\n<td> 0 </td>\n<td> 5 </td>\n</table>\n\nWe can deduce a number of things from this table. First, a DP solution jumps out at us. Let dp[n] be the maximum possible product for integer n. Starting at n=7, we notice that dp[n] = 3*dp[n-3]. We obtain the following **O(n)** solution:\n\n**DP Implementation:**\n\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        case = [0,0,1,2,4,6,9]\n        if n < 7:\n            return case[n]\n        dp = case + [0] * (n-6)\n        for i in range(7, n+1):\n            dp[i] = 3*dp[i-3]\n        return dp[-1]\n```\n\n(Note: we include the base cases for the invalid inputs of n=0 and n=1 to maintain alignment of the indexes of dp, avoiding the need for an offset.)\n\n<br>\n<br>\n\nHowever, we aren\'t done yet. If we look a little more carefully at the above table, we see that the powers of 2 and 3 follow a pattern. \n\nThe "power of 2" pattern is fairly easy to spot. Starting at n=4, the number of 2\'s repeats the cycle of 2,1,0. So the "2 exponent" in the maximum product can be expressed as (-n)%3.\n\nThe "power of 3" pattern is similar, but slightly harder to express. Again, the pattern starts at n=4 and has a period of length 3. This time, the numbers in each cycle are all one more than the numbers in the previous cycle. 0,1,2 , 1,2,3 , 2,3,4 , ... . We figure out that we can express this "3 exponent" as ((n-1)%3) + (n-4)//3. The first term handles the periodic behavior and the second term captures the perpetual increases between cycles.\n\nWe now have an explicit formula to solve the problem, solving in **O(1)** time. Since the only special cases of n=2 and n=3 have maximum products of 1 and 2 respectively, we can handle everything in one line:\n\n**Explicit Formula Implementation:**\n\n```\ndef integerBreak(self, n: int) -> int:\n    return int(math.pow(2, (-n)%3) * math.pow(3, (n-1)%3 + (n-4)//3)) if n > 3 else n-1\n```\n\n(Credit to [totsubo](https://leetcode.com/totsubo/) for correcting my initial error of using ** instead of ```math.pow()``` - we cannot use ** if we want to preserve constant time complexity.)
['Math', 'Dynamic Programming']