leetcode_gym/_problems/arrangeCoins.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Arrange Coins	2020-07-01	binary search	https://leetcode.com/problems/arranging-coins	Attempted

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 k coins.

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

Tried the intuitive solution first but it ran into TLE.

It's actually a binary search question similar to Search Insert Position

There's suppose to be a binary search solution to this but I don't get it. I"m just using the brute force solution.

1
2 3
4 5 6
7 8 9 10


so array would be like:
0 1 2 3 4 5 6 7 8 9 10
0 1 1 2 3 3 3 4 4 4 4 

{% highlight python %}

def arrangeCoins(self, n: int) -> int:

    curr = 0
    count = 0
    
    a = [0]*(n+1)
    
    for i in range(0, n+1):
        a[i] = curr
    
        print(curr, count)
    
        if curr!=count:
            count += 1
        else:
            curr += 1
            count = 0
    
    
    print(a)
    return a[n]

{% endhighlight %}

---

Another solution that worked is from Timonthy H Chang

{% highlight python %}

def arrangeCoins(self, n: int) -> int:

stairs, coins, i = 0,1,1

while coins<=n:
    
    stairs +=1
    i+=1
    coins+=i

return stairs

{% endhighlight %}