This problem maybe have O(1) time complexity,use Derivatives!


  • 0
    E

    first:we can find out the number of n should be divided into with Derivatives;
    the Derivatives of f(x) =(n/x)^x is f'(x)=-(x^-2) * ((n/x)^x) * ln(n/x);
    so the number should be round(n/e) where e=2.7148;
    second :find out the answer according to the number:
    because the number is discrete compared with ’x‘ ,here I make the number=[ floor(n/e)-1 floor(n/e) floor(n/e)+1 ];
    the code below:

    private:
        double mostInt;
        double mostIntCount;
        double leastInt;
        double leastIntCount;
        double e;
    public:
        long long get (double countAll,int n){
            if(countAll<1) return 0;
            mostInt=round(n/countAll);
            mostIntCount=floor(n/mostInt);
            while(countAll-mostIntCount<=0){
                if(n!=mostInt*mostIntCount) mostIntCount--;
                return pow(mostInt,mostIntCount);
            }
            while(int(n-mostInt*mostIntCount)%int(countAll-mostIntCount)!=0)
                mostIntCount--;
            leastIntCount=countAll-mostIntCount;
            leastInt=(n-mostInt*mostIntCount)/leastIntCount;
            while(abs(leastInt-mostInt)!=1){
                mostIntCount--;
                while(int(n-mostInt*mostIntCount)%int(countAll-mostIntCount)!=0)
                    mostIntCount--;
                leastIntCount=countAll-mostIntCount;
                leastInt=(n-mostInt*mostIntCount)/leastIntCount;
            }
            long long a1=pow(mostInt,mostIntCount);
            long long a2=pow(leastInt,leastIntCount);
            return a1*a2;
        }
        int integerBreak(int n) {
            if(n==2) return 1;
            if(n==3) return 2;
            if(n==4) return 4;
            mostInt=0,mostIntCount=0,leastInt=0,leastIntCount=0;
            double e=2.718281828459;
            int countAll=0;
            countAll=floor(n/e);
            long long answer1=get(countAll,n);
            long long answer2=get(countAll+1,n);
            long long answer3=get(countAll-1,n);
            return max(answer3,max(answer1,answer2));
        }
    };

Log in to reply
 

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