Marc Lester Tan

For the month of July, I decided to get back onto "Leetcoding" after almost 2 weeks of hiatus from solving algorithmic problems.

Every month since April this year, Leetcode organizes this 30-day challenge where each day, you have to solve 1 problem. For today, we are going to solve a problem called "Arranging Coins".

My first solution is a brute-force approach where we iterate and consume the coins until we ran out of coins or until the last row cannot be formed correctly anymore (number of coins in the last row is equal or less than the previous row).

class Solution {
    fun arrangeCoins(n: Int): Int {
        if(n == 0) return 0
        var coins = n
        var current = 0
        var rowCount = 0
        
        while(coins > 0) {
            if(current >= coins) break
            coins = coins - (current + 1)
            current++
            rowCount++
            
        }
        
        return rowCount
    }
}

Runtime: 164 ms Memory Usage: 32.1 MB

It works but it's not really optimized. Time complexity is O(n)

Let's try to analyze the problem further.

If I have 5 coins, I can set it up like this:

o       1
o o     1 + 2 = 3
o o     1 + 2 + 2 = 5

For 8 coins:

o       1
o o     1 + 2 = 3
o o o   1 + 2 + 3 = 6
o o     1 + 2 + 3 + 2 = 8

for 10 coins:

o           1
o o         1 + 2 = 3
o o o       1 + 2 + 3 = 6
o o o o     1 + 2 + 3 + 4 = 10

We can observe that in every row, the number of coins that will be used up until the current row is \(n * (n + 1) / 2\).

Let \(k = n * (n + 1)/2\).

We can then use binary search to find k within 0 and the total number of coins.

class Solution {
    fun arrangeCoins(n: Int): Int {
        if(n == 0) return 0
        var low = 0L
        var high = n.toLong()
                
        while(low <= high) {
            val mid = low + (high - low)/2
            val target = (mid * (mid + 1))/2
            
            if(n.toLong() == target) return mid.toInt()
            
            if(n.toLong() > target) low = mid + 1
            else high = mid - 1
        }
        
        return high.toInt()
    }
}

Runtime: 152 ms Memory Usage: 32 MB

Runtime is better than before. The time complexity now becomes O(logn)

But we could still improve this by using simple math. Remember, \(k = n(n + 1)/2\).

By using completing the square technique, we could convert k into:

\[ (n + 1/2)^2 - 1/4 \leq 2k \]

\[ n = \sqrt{2k + 1/4} - 1/2 \]

So our code now becomes:

class Solution {
    fun arrangeCoins(n: Int): Int = (Math.sqrt(2.0 * n + 0.25) - 0.5).toInt()
}

Runtime: 184 ms Memory Usage: 31.9 MB

The runtime is worse than both binary search and brute-force which is weird but time complexity should be O(1).