Solution by zlgrube

• Solution 1: Iterative Subtraction [Accepted]

Intuition

Given a number of coins $$n$$, we will subtract the number of coins in each row k (namely, k coins) from $$n$$ until $$n /leq 0$$. Then we count the number of subtractions we've done, and this is how many full rows we can generate.

Algorithm

class Solution:
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
count = 0 ##subtractions we've performed
row = 1 ##coins in row we are subtracting
while (n >= 0):
n  -= row
row += 1
count += 1
return count-1


This solution clearly has O(1) space complexity. The time complexity is a little tricky to analyze, but luckily, count actually tracks the number of while loops completed. We can use this:
for n = 10, count = 4.
n = 100, count = 13
n = 1,000, count = 44
n = 10,000, count = 140

We observe that each time n jumps an order of magnitude, count is multiplied by approximately 3. This implies an O(n) time complexity.

Solution 2: Direct Computation [Accepted]

Intuition

While the above solution is most "interesting" computationally, as it solves the problem in an organic way, mathematically-inclined solvers might notice that the number of coins consumed in printing $$k$$ rows is simply the sum of integers $$1,2,3...,k$$, which by common result is $$\frac{k(k+1)}{2}$$ (If you haven't seen this proof, it's a valuable first exercise in induction).

So we have
$$n = \frac{k(k+1}{2}$$
$$2n = k^{2} + k$$

Completing the square:

$$2n + 0.25 = k^{2} + k + 0.25$$
$$2n + 0.25 = (k + 0.5)^{2}$$
$$\sqrt{2n + 0.25} - 0.5 = k$$

Thus for $$n$$ coins, we can fill $$\sqrt{2n + 0.25} - 0.5$$ rows. We will floor this to find the number of complete rows, which is done automatically by Python3's cast to int.

Algorithm

class Solution:
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
return int(((2*n)+0.25)**0.5 - 0.5)


This solution runs has O(1) time and space complexity.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.