C++/Python O(log n) Math & MSBF pow||0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n6 is the number what is split into$2+2+2$ or $3+3$.... Which one is better?\nNote $2^3=
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n6 is the number what is split into$2+2+2$ or $3+3$.... Which one is better?\nNote $2^3=8<9=3^2$, so $3+3$ is the most optimal. For integer $n>3$ it is considered  $n=3*k+r$ where r=0, 2, 4\nthen compute\n$$\n3^k*f(r) \\ where \\ f(0)=1, f(2)=2, f(4)=4\n$$\n# Why not 2? Why not 4? Why not other p?\nConsider $n\\equiv 0\\pmod{6}$, observe $2^3=8<9=3^2$, for other $n\\equiv r\\pmod{6}$ is similar. So taking 3 is better than 2.\n\nConsider $n\\equiv 0\\pmod{12}$, observe $4^3=64<81=3^4$, for other $n\\equiv r\\pmod{12}$ is similar. So taking 3 is better than 4.\n\nWhy not other p? It suffices to prove that $$p^3<3^p$$ for $p\\not=3$  a natural number.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(\\log n)$$ pow(3, k) has TC O(log n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Custom pow using Most significant bit first Algorithm\n```\n    int pow(int x, int k){\n        int y=1;\n        bitset<5> bk(k);\n        #pragma unroll\n        for(int i=4; i>=0; i--){\n            y=y*y;\n            if (bk[i]) y*=x;\n        }\n        return  y;  \n    }\n```\n# Code\n```\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        if (n<=3) return n-1;\n        //Note 2^3=8<3^2, n=3*k+r where r=0, 2, 4\n        auto [k, r]=div(n, 3);\n        if (r==1){//Only this needs modification\n            r=4, k--;\n        }\n        int ans=pow(3, k);\n        if (r>0) ans*=r;\n        return ans;\n    }\n};\n\n```\n# Python code\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n<=3: return n-1\n        k,r=divmod(n,3)\n        if r==1:\n            r=4\n            k-=1\n        ans=3**k\n        if r>0: ans*=r\n        return ans\n        \n```
['Math', 'C++', 'Python3']