Arranging Coins

Question

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.

Tags

• Array
• Mathematics
• Binary Search

Thought

Reference: http://bookshadow.com/weblog/2016/10/30/leetcode-arranging-coins/

There are three different approaches:

• Straightforward approach
• Mathematics method
• Binary search method

For the first method, calculate the number of used coins in the loop start from the first step in the stairs until the number of the used coins is larger than the given number n.

For the second method, solve the equation: x ^ 2 + x = 2 * n and the result is x = sqrt(2 * n + 1/4) - 1/2.

For the third method, since the number of the used coins in each step of stairs can form an increase array with specific pattern: array[i] = i * (i + 1) / 2. Thus, we can use binary search here to find the result

Code

Find in the loop

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        level = 0
        count = level
        while count <= n:
            level += 1
            count += level
        return level - 1

Mathematics

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

Binary Search

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 0, n
        while l <= r:
            m = (l + r) / 2
            if m * (m + 1) / 2 > n:
                r = m - 1
            else:
                l = m + 1
        return r