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


  • 1
    B

    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;
        }
    };
    ···

  • 0
    M

    wonderful idea!


Log in to reply
 

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