Domain 1EasyCORE

Arranging Coins

The problem asks us to determine how many full staircase rows can be formed with `n` coins, where the k-th row must contain exactly `k` coins. The input is a non-negative integer `n`, and the output should be an integer representing the number of complete rows.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#Binary Search

441. Arranging Coins

Model: qwen2.5-coder:14b
Topics: Math,Binary Search
FAANG asked: 0
Acceptance rate: 42.6%


Problem Breakdown

The problem asks us to determine how many full staircase rows can be formed with n coins, where the k-th row must contain exactly k coins. The input is a non-negative integer n, and the output should be an integer representing the number of complete rows.

Inputs:

  • A single non-negative integer n.

Outputs:

  • An integer representing the number of full staircase rows that can be formed.

Implicit Constraints:

  • If n is 0, no rows can be formed.
  • The solution should handle large values of n efficiently, as it fits within a 32-bit signed integer range.

Intuition

A brute-force approach would involve iteratively subtracting the number of coins needed for each row from n until we can’t form another complete row. However, this approach is inefficient with a time complexity of O(√n) because the sum of the first k natural numbers is approximately k^2/2.

The key insight is to use binary search to find the largest integer k such that the sum of the first k natural numbers (i.e., k*(k+1)/2) is less than or equal to n. This reduces the time complexity to O(log n).

Approach

We will use binary search to efficiently find the maximum number of full staircase rows. The steps are as follows:

  1. Initialize two pointers, left and right, where left is 0 and right is n.
  2. While left is less than or equal to right:
    • Calculate the middle point mid.
    • Compute the sum of the first mid natural numbers using the formula k*(k+1)/2.
    • If this sum is less than or equal to n, it means we can form at least mid rows, so move left to mid + 1.
    • Otherwise, if the sum exceeds n, move right to mid - 1.
  3. The answer will be right, which represents the largest number of full staircase rows that can be formed.

Complexity Analysis

  • Time Complexity: O(log n) because we are using binary search.
  • Space Complexity: O(1) as we are only using a few extra variables regardless of the input size.

Solution

def arrangeCoins(n: int) -> int:
    left, right = 0, n
    
    while left <= right:
        mid = (left + right) // 2
        # Calculate the sum of the first mid natural numbers
        total = mid * (mid + 1) // 2
        
        if total == n:
            return mid
        elif total < n:
            left = mid + 1
        else:
            right = mid - 1
    
    return right

Edge Cases Handled

  • n = 0: The function returns 0, as no rows can be formed with zero coins.
  • n = 1: The function returns 1, as a single coin forms one complete row.
  • Large n: The binary search ensures that the solution is efficient even for large values of n within the 32-bit signed integer range.