My O(1) C++ Solution


  • 0
    T

    So it is all about math, and the magic number 2 and 3. The main idea is to have as many 3's as possible when n is greater than 4.

    class Solution {
    public:
        int integerBreak(int n) {
            if(n < 2) return 0;
            if(n == 2) return 1;
            if(n == 3) return 2;
            if(n == 4) return 4;
            int count_three = (n - n % 3) / 3;
            if(n % 3 == 1) return pow(3.0f, count_three - 1) * 4;
            else if(n % 3 == 2) return pow(3.0f, count_three) * 2;
            else return pow(3.0f, count_three);
       }
    };

Log in to reply
 

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