Arranging Coins

Difficulty: Easy | Acceptance: 48.20% | Paid: No Topics: Math, Binary Search

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith 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.

• Examples
• Constraints
• Approach 1: Linear Simulation
• Approach 2: Binary Search
• Approach 3: Math Formula

Examples

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.

Constraints

1 <= n <= 2³¹ - 1

Approach 1: Linear Simulation

Intuition We can simulate the process of building the staircase row by row. We keep subtracting the required number of coins for the current row from the total coins until we run out.

Steps

• Initialize a variable i to 1 representing the current row number.
• Loop while n is greater than or equal to i.
• Subtract i from n and increment i.
• When the loop breaks, i - 1 is the number of complete rows formed.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        i = 1
        while n >= i:
            n -= i
            i += 1
        return i - 1

Complexity

• Time: O(√n) — The loop runs approximately √(2n) times.
• Space: O(1) — We only use a few variables.
• Notes: Simple to implement but less efficient than mathematical approaches for very large n.

Approach 2: Binary Search

Intuition The total number of coins required to build k complete rows is given by the sum of the first k natural numbers: S = k * (k + 1) / 2. We need to find the maximum k such that S <= n. Since S increases monotonically with k, we can use binary search to find this k efficiently.

Steps

• Initialize left to 1 and right to n.
• Perform binary search while left <= right.
• Calculate mid and the total coins coins = mid * (mid + 1) / 2.
• If coins == n, return mid.
• If coins < n, move left to mid + 1 and store mid as a potential answer.
• If coins > n, move right to mid - 1.
• Return the stored answer.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 1, n
        ans = 0
        while left <= right:
            mid = left + (right - left) // 2
            coins = mid * (mid + 1) // 2
            if coins == n:
                return mid
            elif coins < n:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans

Complexity

• Time: O(log n) — Standard binary search complexity.
• Space: O(1) — Constant extra space.
• Notes: Care must be taken with integer overflow when calculating mid * (mid + 1) in languages like Java and C++, so use 64-bit integers (long).

Approach 3: Math Formula

Intuition We can solve the quadratic equation derived from the sum formula k(k + 1) / 2 = n. This leads to k² + k - 2n = 0. Using the quadratic formula k = (-1 + √(1 + 8n)) / 2, we can compute the result directly.

Steps

• Calculate the discriminant delta = 1 + 8 * n.
• Compute the square root of delta.
• Apply the formula k = (-1 + sqrt(delta)) / 2.
• Return the floor of k as the integer result.

import math

class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int((math.sqrt(8 * n + 1) - 1) // 2)

Complexity

• Time: O(1) — Involves a fixed number of arithmetic operations.
• Space: O(1) — No extra space used.
• Notes: This is the most optimal solution, though floating-point precision issues could theoretically arise with extremely large integers, though not within the constraints of this problem (2³¹ - 1).