Easy to understand O(1) JAVA

  • 0

    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

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

  • 0

    @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.