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
nis 0, no rows can be formed. - The solution should handle large values of
nefficiently, 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:
- Initialize two pointers,
leftandright, whereleftis 0 andrightisn. - While
leftis less than or equal toright:- Calculate the middle point
mid. - Compute the sum of the first
midnatural numbers using the formula k*(k+1)/2. - If this sum is less than or equal to
n, it means we can form at leastmidrows, so movelefttomid + 1. - Otherwise, if the sum exceeds
n, moverighttomid - 1.
- Calculate the middle point
- 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
nwithin the 32-bit signed integer range.