algoadvance

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the i-th row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Example 1:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

Example 2:

Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.

Clarifying Questions

  1. Should I handle negative inputs or non-integer inputs?
    • No need. Assume n is always a non-negative integer.
  2. Can n be zero?
    • Yes, in which case the output should be 0.

Strategy

To determine the number of complete rows that can be built with n coins, we need to find the maximum k such that the sum of the first k natural numbers (i.e., 1 + 2 + ... + k) is less than or equal to n.

The sum of the first k natural numbers is given by the formula:

[ \text{Sum}(k) = \frac{k \cdot (k + 1)}{2} ]

We need to solve the inequality:

[ \frac{k \cdot (k + 1)}{2} \leq n ]

This can be simplified to:

[ k^2 + k \leq 2n ]

Which is a quadratic equation in the form:

[ k^2 + k - 2n = 0 ]

Using the quadratic formula ( k = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} ), where ( a = 1 ), ( b = 1 ), and ( c = -2n ), we get:

[ k = \frac{-1 \pm \sqrt{1 + 8n}}{2} ]

Since k must be a positive integer, we take the positive root:

[ k = \frac{-1 + \sqrt{1 + 8n}}{2} ]

The largest integer value of k that satisfies this will be the number of complete rows.

Code

import math

def arrangeCoins(n: int) -> int:
    if n == 0:
        return 0
    # Quadratic formula to solve for k
    k = int((-1 + math.isqrt(1 + 8 * n)) // 2)
    return k

Time Complexity

The time complexity of the above approach is ( O(1) ) because we are performing a constant number of arithmetic operations, including a square root calculation.

Try our interview co-pilot at AlgoAdvance.com