Coin Change Problem in Kotlin: Multiple Approaches with Examples

The coin change problem is a classic leet coding challenge often encountered in technical interviews. The problem asks:

Given an array of coin denominations and a target amount, find the fewest number of coins needed to make up that amount. If it's not possible, return -1. You can use each coin denomination infinitely many times.

Here are multiple ways to solve the Coin Change problem in Kotlin, with detailed explanations and code examples. I'll present two distinct approaches:

1. Dynamic Programming (Bottom-Up approach)
2. Recursive Approach with Memoization (Top-Down)

---

Approach 1: Dynamic Programming (Bottom-Up)

Idea:

• Build an array dp where each dp[i] indicates the minimum number of coins required for the amount i.
• Initialize the array with a large number (representing infinity).
• The base case is dp[0] = 0.

Steps:

• For each amount from 1 to amount, try every coin denomination.
• Update dp[i] if using the current coin leads to fewer coins than the current value.

Kotlin Solution:

fun coinChange(coins: IntArray, amount: Int): Int {
    val max = amount + 1
    val dp = IntArray(amount + 1) { max }
    dp[0] = 0

    for (i in 1..amount) {
        for (coin in coins) {
            if (coin <= i) {
                dp[i] = minOf(dp[i], dp[i - coin] + 1)
            }
        }
    }
    
    return if (dp[amount] > amount) -1 else dp[amount]
}

// Usage:
fun main() {
    println(coinChange(intArrayOf(1, 2, 5), 11)) // Output: 3
    println(coinChange(intArrayOf(2), 3))        // Output: -1
    println(coinChange(intArrayOf(1), 0))        // Output: 0
}

Time Complexity: O(amount * coins.length)
Space Complexity: O(amount)

---

Approach 2: Recursive Approach with Memoization (Top-Down)

Idea:

• Define a recursive function solve(remainingAmount) that returns the minimum coins required.
• Use memoization to store previously computed results, avoiding redundant calculations.

Steps:

• For each call, explore all coin denominations and recursively find solutions.
• Cache results to avoid recomputation.

Kotlin Solution:

fun coinChangeMemo(coins: IntArray, amount: Int): Int {
    val memo = mutableMapOf<Int, Int>()

    fun solve(rem: Int): Int {
        if (rem < 0) return -1
        if (rem == 0) return 0
        if (memo.containsKey(rem)) return memo[rem]!!

        var minCoins = Int.MAX_VALUE
        for (coin in coins) {
            val res = solve(rem - coin)
            if (res >= 0 && res < minCoins) {
                minCoins = res + 1
            }
        }

        memo[rem] = if (minCoins == Int.MAX_VALUE) -1 else minCoins
        return memo[rem]!!
    }

    return solve(amount)
}

// Usage:
fun main() {
    println(coinChangeMemo(intArrayOf(1, 2, 5), 11)) // Output: 3
    println(coinChangeMemo(intArrayOf(2), 3))        // Output: -1
    println(coinChangeMemo(intArrayOf(1), 0))        // Output: 0
}

Time Complexity: O(amount * coins.length)
Space Complexity: O(amount) (stack space + memoization map)

---

Quick Comparison:

Approach	Time Complexity	Space Complexity	When to Use?
Dynamic Programming (Bottom-Up)	O(amount * coins.length)	O(amount)	Optimal, preferred for efficiency
Recursive with Memoization	O(amount * coins.length)	O(amount)	Easy to understand recursion

---

Edge Cases Handled:

• If amount is 0, both solutions immediately return 0.
• If the amount cannot be composed by given coins, they return -1.

---

Summary:

• Dynamic Programming is the optimal, most widely used solution for this problem.
• Recursive Approach with memoization demonstrates understanding of recursion and memoization principles.

You can select either based on clarity, readability, or efficiency needs. The DP solution is highly recommended in competitive programming or technical interviews for optimal performance. 

Thanks for reading! 🎉 I'd love to know what you think about the article. Did it resonate with you? 💭 Any suggestions for improvement? I’m always open to hearing your feedback to improve my posts! 👇🚀. Happy coding! 💻✨