C++ 1 line code


  • 0
    K

    Let me know if anyone need explanation :)

    int arrangeCoins(int n) {
        return (int)floor((long long)(floor(sqrt(1LL + 8LL * n)) - 1LL) >> 1LL);
    }
    

  • 0
    Y

    Please explain your solution.


  • 0
    C

    A slightly easier to understand version would be

    return (int(sqrt((8*(long long)n+1)))-1)/2;
    

    Here comes the explanation:
    First lets define Nk as a function return n coins of full stairs with height k .
    i.e.

    N3=6;
    N4=10; 
    

    We know that

    Nk=(k+1)*k/2;
    

    solve this equation we will get

    k=((8Nk+1)^(0.5)-1)/2;
    

    because from Nk=(k+1)*k/2

        2Nk = k^2+k       
    

    then

        8Nk = 4*k^2+4*k
    
    

    then

        8Nk+1 = (2k+1)^2;
    

    then

        k = (sqrt(8Nk+1)-1)/2;
    

    to use n instead of Nk

        k = (int(sqrt(8n+1))-1)/2
    

    Finally if you use

    return (int(sqrt((8*n+1)))-1)/2;
    

    You will find there are some test cases with very large n such that 8*n would overflow, then you will using
    long long to prevent overflow.

    end of in the end
    using right shift >>1 instead of /2.

    Thanks kaidul, you idea is exactly same with me. :P


  • 0
    Y

    Thanks cdrover


Log in to reply
 

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