Easy to understand O(1) JAVA


  • 0
    M

    We need the smallest x such that 1+2...+x is smaller than n. Therefore we need smallest x such that x(x+1)/2 <= n. Hence the closest guess for x is square root of 2*n. We test if it's good by plugging it in the original condition. If it is too big we substract 1.

    public int arrangeCoins(int n) {
            int x =(int) Math.sqrt(2L*n);
            return x*(x+1L)<=2L*n? x : x-1;
        }

  • 1
    U

    x*(x+1) <= 2*n
    it may be overflow, don't you care about it?


  • 0
    M

    @uni691125 Thanks for reminding me ;) Fixed.


Log in to reply
 

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