1-Line quadratic equation formula with additional overflow discussion


  • 0

    The problem is equivalent to math problem: find max integer k such that k(k+1) <= 2n. Then it is straightforward to use root formula of quadratic equation ax^2+bx+c = 0 which is
    r = (-b+/-sqrt(b^2-4ac))/2, where negative root is ignored.
    However, the interesting part of this problem, I think, is how to handle overflow and numeric accuracy. The max value during the formula calculation is 8*n+1, where n is inttype. If we do not use (long) to get a higher overflow upper bound, I was trying to reformulate the expression as 1.5*sqrt(8*(n/9.0)+1.0/9.0)-0.5, which guarantees no overflow in int range. However, this suffers loss of accuracy when the given n happens to form a complete staircase (e.g., n=6) and therefore gives off-by-1 results. Not sure whether we have other solutions using the formula without casting to long. Any comment is appreciated!

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

Log in to reply
 

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