Solution by zlgrube


  • 0
    Z

    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.


Log in to reply
 

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