O(1) time O(1) space c++ solution, possibly shortest and fastest


  • 7
    int maxA(int N) {
        if (N <= 6) return N;
        if (N == 10) return 20;
        int n = N / 5 + 1, n3 = n * 5 - 1 - N;
        return pow(3, n3) * pow(4, n - n3);
    }
    

    Pure math. This problem is to partition number N into 3's and 4's and get their product. n = N / 5 + 1 is to compute the number of factors(the total number of 3's and 4's). With n, it's easy to know how many out of them are 3's by computing n3 = n * 5 - 1 - N. We minus 1 here because adding a single factor requires one step more than the factor itself, e.g. x4 takes 5 steps (select all, copy, paste, paste, paste). 10 is special here because it's the only > 6 number where there is no enough factors to share cuts from decrement of the number of 3's which means a 5 has to be introduced.


  • 0
    X

    This is amazing!


  • 0
    X
    This post is deleted!

  • 0
    S

    Could you explain a little why n = N / 5 + 1 is to compute the total number of 3's and 4's ?


Log in to reply
 

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