Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Pyramid height

Given a certain number of blocks N, your program must return the height of the tallest possible 2D pyramid that can be created, followed by the number of unused blocks remaining.

For example, a pyramid of height 3 contains 6 blocks: 3 for the first level, 2 for the second level and 1 for the last level.

INPUT:

Line 1: An integer N, the number of blocks to be used for the pyramid.

OUTPUT:

Line 1: Two integers H and R, where H is the greatest possible pyramid height, and R is the remaining unused blocks.

CONSTRAINTS:

0 ≤ N < 50000

EXAMPLE:

Input

10

Output

4 0

Solution

When going the pyramid from top to bottom, we need to sum \(1+2+3+4+...\). Since we have \(n\) blocks given, it follows:

\begin{array}{rrl}& n &\geq \sum\limits_{i=1}^h i\\\Leftrightarrow & n &\geq \frac{1}{2}h(h+1)\\\Leftrightarrow & 2n &\geq h^2+h\\\Leftrightarrow & 2n+\frac{1}{4} &\geq (h+\frac{1}{2})^2\\\Leftrightarrow & \sqrt{2n+\frac{1}{4}} &\geq h+\frac{1}{2}\\\Leftrightarrow & \sqrt{2n+\frac{1}{4}}-\frac{1}{2} &\geq h\\\Leftrightarrow & \frac{1}{2}\left(\sqrt{8n+1}-1\right) &\geq h\\\Leftrightarrow & h &= \left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil\end{array}

That was the first term. Since \(n = r + \sum\limits_{i=1}^h i\) follows, that \(r= n - \frac{1}{2}h(h+1)\). We now have all pieces together and can implement the thing. In Ruby this can look like:

N=gets
H=ceil((sqrt(8*N+1)-1)/2)
R=N-H*(H+1)/2
p [H,R].join(" ")

It's quite short already. I think some bytes can be stripped off by simply looping down the pyramid. But I prefer this \(O(1)\) solution (seeing sqrt as constant).

Go to overview