Question

Given an integer a representing the square blocks. The height of each square block is 1. The task is to create a staircase of max height using these blocks. The first stair would require only one block, the second stair would require two blocks and so on.

Answer 1

Answer:

There's no need for recursion or dynamic programming here; it's just a bit of maths.

If you take i steps on each turn, you will take (n * (n+1)) / 2 steps. You will land on the k-th step if k is an integer solution to the equation:

k = (n * (n+1)) / 2

Rearranging:

0 = n^2 + n - 2*k

which is a quadratic equation in n:

n = (-1 +/- sqrt(1 + 4*1*2*k)) /