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.
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 <= 231 - 1This approach involves sequentially counting how many coins are required to form a complete row one row at a time. While the number of available coins is greater than or equal to coins needed for the next row, continue adding rows and reducing the count of available coins accordingly.
The solution involves a while loop that continues to subtract sequential numbers from n. Each time a subtraction is successful, the count of complete rows (k) is incremented. The loop terminates when n is less than the number of coins needed for the next row.
C++
Java
Python
C#
JavaScript
Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically.
Space Complexity: O(1), constant space is used.
Using a binary search, optimize the process of finding the maximum k where the sum of the first k natural numbers is less than or equal to n. Calculate mid values and determine if they result in a possible sum being less or equal to n and adjust the search space accordingly.
The C code employs long integers for intermediate calculations to avoid overflow. The binary search algorithm adjusts the search range based on whether the calculated sum of coins (for k = mid) is greater or less than n.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Iterative Solution | Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically. |
| Approach 2: Binary Search | Time Complexity: O(log n) |
Arranging Coins - Leetcode 441 - Python • NeetCode • 42,249 views views
Watch 9 more video solutions →Practice Arranging Coins with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor