Problem
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly kcoins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.
Solution: Math
Time complexity: O(sqrt(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Running time: 16 ms class Solution { public: int arrangeCoins(int n) { for (long i = sqrt(n) * 2 + 1; i >= 0; --i) if (i * (i + 1) / 2 <= n) return i; return -1; } }; |
Time complexity: O(1)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua // Running time: 12 ms class Solution { public: int arrangeCoins(int n) { // x * (1 + x) / 2 <= n // x^2 + x - 2n <= 0 // x <= (-1 + sqrt(1 + 8n)) / 2 return (-1 + sqrt(1 + static_cast<long>(n) * 8)) / 2; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment