382. Coin Staircase
A street performer builds a staircase out of coins on a table. The first step is a row of 1 coin, the second step is a row of 2 coins, the third is a row of 3 coins, and so on, each row one coin longer than the last. He only counts a step if its row is complete.
Given the number of coins n he owns, return how many complete steps he can build. The last step may be unfinished, and in that case it is not counted. The value of n can be as large as 2^31 - 1, so the total number of coins used by k steps, k * (k + 1) / 2, may overflow a 32-bit integer. A solution that adds the steps one at a time is allowed, but an O(log n) solution is expected.
Example 1
- Input:
- n = 10
- Output:
- 4
- Explanation:
Steps of 1, 2, 3 and 4 coins use exactly 10 coins, so 4 steps are complete.
Example 2
- Input:
- n = 14
- Output:
- 4
- Explanation:
Four steps use 10 coins and the fifth needs 5 more, but only 4 are left, so the answer is 4.
Constraints
1 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)