C++ 0 ms no loops


  • 0
    P

    Max product gives you a sum of 3th + the rest:

    7: 3 + 4 (rest == 4)

    8: 3 + 3 + 2 (rest == 2)

    9: 3 + 3 + 3 (rest == 0)

    10: 3 + 3 + 4 (rest == 4)

    What you need to do is get number of 3-th in the n: n/3

    Then check the rest: n%3. Possible values of n%3:

    If rest is 0 - ignore it (9%3 ==0, 3+3+3 -> 3 * 3 * 3 == 27 )

    If rest is 2 - use it (3 + 3 + 2 -> 3 * 3 * 2 = 27 )

    if rest is 1 - 1 doesn't increase your product since for example 9 * 1 == 9

    so "merge" 1 with one of 3th summing 3 with that 1.

    For example:

    7: 3+3+1 gives you 3 * 3 * 1= 9

    so do: 3 + (3+1) -> 3 * 4 then 3 * 4 gives you 12.

    That's it...

    int integerBreak(int n) 
    {
        if(n == 2)
            return 1;
        if(n == 3)
            return 2;
            
        int rest = n % 3;
        int numof3th = n / 3;
        if(rest == 1)
        {
            rest  = 4;
            --numof3th; 
        }
        
        int product = pow(3, numof3th) * ((rest == 0) ? 1 : rest);
        return product;
    }

  • 0
    A

    int integerBreak(int n) {
    int A[2] = {1, 2};
    int B[3] = {3, 4 ,6};
    int m = 1;

    if(n < 4)return A[n-2];
    for(int i = 0; i < (n/3 - 1); ++i)m = m *3;
    return m * B[n % 3];
    

    }


Log in to reply
 

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