C++ Simple Math 0ms Solution with Explanation
Approach:\n\n If the product contains a factor f >= 4, then we can always replace it with factors 2 and f-2 without losing optimality\n\t as 2*(f-2) = 2f-4 >= f
**Approach:**\n\n* If the product contains a factor f >= 4, then we can always replace it with factors 2 and f-2 without losing optimality\n\t* as ```2*(f-2) = 2f-4 >= f```\n* So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3\n\t* and 1 is of course wasteful and you\'d only use it for n=2 and n=3, where it\'s needed\n* we will prefer 3 for n>4\n\t* why?\n\t\t* for n = 6\n\t\t* ```6 = 2 + 2 + 2 = 3 + 3. But 2 * 2 * 2 < 3 * 3```\n\t\t* Therefore, if there are three 2\'s in the decomposition, we can replace them by two 3\'s to gain a larger product.\n\t\t* similarly, if we have two 2\'s and one 1 then we can replace them by one 2 and one 3 as in the case of 5\n\t\t* ``` 5 = 2+2+1=2+3 but 2*2*1<2*3```\n* so just calculate the n%3 =m\n\t* if m==0\n\t\t* we can have all factors as 3\n\t* if m==1\n\t\t* we will take (k-1) 3\'s and one 4\n\t* if m==2\n\t\t* we will take k 3\'s and one 2\n\n**Code:**\n\n```\nclass Solution\n{\npublic:\n    int integerBreak(int n)\n    {\n        if (n == 2)\n            return 1;\n        if (n == 3)\n            return 2;\n        if (n == 4)\n            return 4;\n        int k = n / 3;\n        int m = n % 3;\n        int ans;\n        if (m == 0)\n            ans = pow(3, k);\n        else if (m == 1)\n            ans = pow(3, k - 1) * 4;\n        else if (m == 2)\n            ans = pow(3, k) * m;\n        return ans;\n    }\n};\n```
['Math', 'Dynamic Programming', 'C', 'C++']