441.Arranging Coins

Tags: [implementation], [simulation]

Link: https://leetcode.com/problems/arranging-coins/?tab=Description

You have a total ofncoins that you want to form in a staircase shape, where everyk-th row must have exactlykcoins.

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: simulation

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            raise ValueError('the input is invalid')
        if n == 0:
            return 0

        counter = 0
        row = 1
        while n - row >= 0:
            n -= row
            counter += 1
            row += 1

        return counter

Revelation:

• When we calculate the time complexity, we can list some or all the processes, and write out the formula, then may use the math to calculate and simplify the formula.

Note:

• Time complexity = O(sqrt(n)), n is the given number.
• The explanation of the time complexity: we do the following processes: (n - 1), (n - 1 - 2), (n - 1 - 2 - 3)...(n - 1 - 2 - 3... - k), so n = 1 + 2 + 3 + ... + k, n = (1 + k) * k, so k = sqrt(n / 2) - 1/2. Because the number of processes is equal to k, so the time complexity = O(k), so time complexity = O(sqrt(n)).