We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Arranging Coins

Difficulty: Easy

Problem Description

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.

Key Insights

  • The number of coins required for k complete rows is given by the formula: k * (k + 1) / 2.
  • We need to find the largest integer k such that k * (k + 1) / 2 <= n.
  • This is a classic problem that can be solved using binary search due to the monotonic nature of the function.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

To solve this problem, we can use binary search to efficiently find the maximum number of complete rows that can be formed with n coins. We define the search space from 1 to n and repeatedly narrow down the possible number of rows (k) by checking if the total coins required for k rows exceeds n. If it does, we adjust our search to lower values; otherwise, we look for higher values.

Code Solutions

def arrangeCoins(n: int) -> int:
    left, right = 1, n
    while left <= right:
        mid = (left + right) // 2
        total_coins = mid * (mid + 1) // 2
        if total_coins == n:
            return mid  # Found the exact number of rows
        elif total_coins < n:
            left = mid + 1  # Increase the number of rows
        else:
            right = mid - 1  # Decrease the number of rows
    return right  # The last valid row count
← Back to All Questions