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! 💻✨

Read More

Problem and Solution: Background ListView becomes black when scrolling after populated data on list

I have faced background ListView becomes black when scrolling after populated data on list, after that i have  found easy solution from stackoverflow.


Add an attribute on the ListView Tag

android:cacheColorHint="#00000000"

More details about this problem, go to android blog: http://android-developers.blogspot.com/2009/01/why-is-my-list-black-android.html

or alternate solutions , may be if the above trick not working then try this:

It's very simple just use this line in your layout file :

android:scrollingCache="false"

l
ike this:

<ListView 
android:layout_width="fill_parent"
android:layout_height="fill_parent"
android:scrollingCache="false"
/>

finally, both of the above not working try this also:

list.setCacheColorHint(Color.TRANSPARENT);
list.requestFocus(0);

if all the above not working then please visit:  http://developer.android.com/reference/java/util/List.html
and
http://developer.android.com/guide/topics/ui/layout/listview.html

Happy Coding!!!

Read More