Arranging Coins Python Solution with Tests

LeetCode 441, Easy. Topics: Math, Binary Search. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 19 parametrized pytest cases, and a playground notebook:

lcpy gen -n 441   # by problem number
lcpy gen -s arranging_coins   # by problem name

Problem

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the i^th 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.

Examples

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.

Constraints

1 <= n <= 2^31 - 1

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from math import isqrt


class Solution:
    # Time: O(1)
    # Space: O(1)
    def arrange_coins(self, n: int) -> int:
        # largest k with k * (k + 1) / 2 <= n
        return (isqrt(8 * n + 1) - 1) // 2

Complexity

Time	Space
O(1)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Arranging Coins Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags