# Java O(1) Solution - Math Problem

• The idea is about quadratic equation, the formula to get the sum of arithmetic progression is
sum = (x + 1) * x / 2
so for this problem, if we know the the sum, then we can know the x = (-1 + sqrt(8 * n + 1)) / 2

public class Solution {
public int arrangeCoins(int n) {
return (int)((-1 + Math.sqrt(1 + 8 * (long)n)) / 2);
}
}

• Nice! Was looking for this: sum = (x + 1) * x / 2

• @mysun Doubt that Math.sqrt() is O(1).

• @WKVictor Java's Math.sqrt actually delegates sqrt to StrictMath.java source code which be found here, it loops 52 times. Look at while(r != 0) loop inside.

• @mysun Sorry that I am not a Java programmer. I mean, generally speaking, sqrt seems not O(1). But you found the proof for your claim. Good job!

• @mysun You think LeetCode is using the GNU Classpath implementation? From over 9 years ago?

I and probably most people know and understand the (x + 1) * x / 2 formula, but can you explain the (-1 + sqrt(8 * n + 1)) / 2 formula?

• @StefanPochmann
(1 + X) * X = 2n
4X * X + 4 * X = 8n
(2X + 1)(2X + 1) - 1 = 8n
X = (Math.sqrt(8 * n + 1) - 1)/ 2

• @weihanzh Nice, thanks. I just had to add the inequalities to completely convince me:

If x is the answer, then n coins do fill x rows but don't fill x+1 rows. So we have x(x+1)/2n < (x+1)((x+1)+1)/2. Which, using the other formula, turns into x(sqrt(8n+1) - 1) / 2 < x+1. So we indeed get the right answer by rounding down (sqrt(8n+1) - 1) / 2.

• @StefanPochmann No problem :)

• @StefanPochmann

@mysun You think LeetCode is using the GNU Classpath implementation? From over 9 years ago?

I and probably most people know and understand the (x + 1) * x / 2 formula, but can you explain the (-1 + sqrt(8 * n + 1)) / 2 formula?

The equation comes from here:

And the negative solution is ignored

• @HongbiaoYang thank you for the explanation, i mistakenly thought there was some other formula to solve quadratic inequality function.

• I can understand the math but why we need

(long)

since I found it doesn't work without it ？

• @Archonzzb
cuz n is int so 8*n may overflow

• Great Solution Bravo!

• I got the same idea at the first look. Glad to see someone has posted that.

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

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