Java one line math solution,O(1)


  • 1
    D

    For example:

    public int arrangeCoins(int n) {
    return (int) (-1.0 + Math.sqrt((8L * n) + 1)) >> 1;
    }
    

    Explain:
    using the formule of delta,
    x= (-b(+-)sqrt(b^2 - 4ac) ) / 2a
    as we know,the sequence of number is regular like:
    an-an-1 = n-1;
    an-1 - an-2 = n-2;
    an-2 - an-3 = n-3;
    .
    .
    .
    .
    a3 - a2 = 2;
    a2-a1 = 1;

    so,we can accumulate above sequences,then

    an-a1 = (1+2+3+....+n-1)

    simplify

    an = (n^2-n) /2 + a1 ,and a1 = 1 (the head of the sequence for each row,and we define the head as an0,tail is ann)

    so

    ann = an0 + n-1 = (n^2-n)/2 + n;

    simplify

    X = (n^2-n)/2 + n

    double

    2X = n^2-n + 2n,

    so,

    n^2+n-2X = 0;

    so we can use the formule of delta:

    x= (-b(+-)sqrt(b^2 - 4ac) ) / 2a

    that is the result for the problem


Log in to reply
 

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