O(1) Solution. Why O(n)?


  • 0
    Y

    Based on the hint, I think we'd better divide n to 3's + 2's to get maximum. So we can do it in O(1) time. The following is my accepted answer.

    class Solution {
    public:
        int integerBreak(int n) {
            if (n <= 3) return n-1;
            int ret = 1;
            int mod = n%3;
            if ( mod == 1)
            {
                n -= 4;
                ret = 4;
            }
            ret *= pow(3, n/3) * (mod ? mod : 1);
            return ret;
        }
    };
    

  • 0
    Y

    Just saw one more compact solution from dehuaguo-gmail-com
    https://discuss.leetcode.com/topic/73751/5-lines-o-1-c

    public:
        int integerBreak(int n) {
            if(n <= 3) return n-1;
            if(n%3 == 1) return pow(2,2) * pow(3,n/3-1);
            if(n%3 == 2) return pow(2,1) * pow(3,n/3);
            return pow(3,n/3);
        }
    };
    

Log in to reply
 

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