Java fast O(1) actually only two possible value


  • 0

    We know the equation is
    row*(row+1) <= 2n;
    Let's denote Double s = sqrt(2
    n)
    Since s*(s+1) = s^2+s = 2n+1 > 2n and (s-0.5)*(s-0.5+1) = s^2-0.025 < 2n, so the Double type root is between s and s-0.5 and the integer answer will be the biggest integer <= that root;
    So the answer can only be (int) s or (int) s-1 because:

    1. if s round up: (int) s is exclusive upper bound because it's even bigger than s and (int) s-1 is inclusive lower bound because s-1 < s-0.5
    2. if s round down: (int) s +1 is exclusive upper bound and (int) s -1 is inclusive lower bound
    public static int arrangeCoins(int n) {
            long m = ((long) n) * 2, x = (long) Math.sqrt(m);
            return x*x+x > m ? (int) x-1 : (int) x;
        }
    

Log in to reply
 

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