# C++ 0ms O(1) solution With explanation

• Let me illustrate the regularity
n=1: return 1
n=2: return 1 (1+1)
n=3: return 2 (1+2)
n=4: return 4 (2+2)
n=5: return 5 (2+3)

Actually when n is bigger than 5, there is a regularity

n=6: return 9 (3+3)
n=7: return 12 (3+2+2)
n=8: return 18 (3+3+2)
n=9: return 27 (3+3+3)
n=10: return 36 (3+3+2+2)
n=11: return 54 (3+3+3+2)
n=12: return 81 (3+3+3+3)

we can see that if the remainder when n is divided by 3 is 0, the maximum product is consists of no two and all three; if the remainder is 1, the maximum product is consists of 2 two and the others are three; if the remainder is 2, the maximum product is consists of 1 two and the others are three.

``````class Solution {
public:
int integerBreak(int n) {
if(n==1) return 1;
if(n<=3) return n-1;
if(n==4) return 4;
if(n==5) return 6;
int n_2 = n%3;
if(n_2==0) return pow(3,n/3);
if(n_2==1) return pow(3,(n-4)/3)*4;
else return pow(3,(n-2)/3)*2;
}
};
···``````

• wonderful idea!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.