How to Solve Coin Change Problem?

Given an array of coins and a total sum, find the fewest number of coins needed to make the sum. Return -1 if impossible.

[{"selector":"#anim-5fec4eb3-ecf6-48dd-8996-315e6c78ae70","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-f1ea4fb2-3ba9-4db9-8c97-e4b08d722949","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-3643fd0a-bb31-4914-93c6-7ca8038b7ea2 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-647f5454-eaef-404e-b017-07b7133c7c9c","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-a49fc4bb-5ba6-4a93-ac7b-d2e208c07a20","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Explore now

Example- Input: [1,2,5,9,8] Sum: 17 Output: 2 Explanation: Two coins require to make the desired sum [9,8]

[{"selector":"#anim-5f1d4d44-339c-41ec-ad75-24bd2f37ddaa [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-034ef67f-2af7-4fd0-89bc-5232790bd83d","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-92e81889-4f0f-426b-a87c-df469a4d4810","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Explore more examples

Use recursion to check all possible combinations of coins to find the minimum number of coins needed to create the given sum. Update the number of coins needed with each iteration.

[{"selector":"#anim-4243953e-6ca4-441a-a7eb-a934d3881490","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-a1cea293-68b7-42cf-92cf-71cca11bf1eb","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-e91a9091-d788-4237-b6eb-2b3908bd1b59 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-6d423f63-8c1d-48a4-8218-e080f945fb50","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-d385c560-61d6-4eff-94c2-c0116404e3cd","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] See code implementation

Time complexity: Exponential. (every recursive call is making n recursive calls) Space complexity: O(1)

[{"selector":"#anim-6ca8f587-405a-4bd5-a165-5c658d6f12e3 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-2982b9d0-1795-4823-b7b6-dd65e77e849e","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-dccc3857-a790-456c-aa9b-00cce21362c0","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Explore other approach

Solve the problem by breaking it down into smaller subproblems and using a bottom-up approach to compute dp[i] (1<=i<=subproblems) which stores the minimum number of coins needed to create the sum.

[{"selector":"#anim-979cbea8-fa86-49f0-bda9-02aaea13af9b","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-5e02eed2-31d7-482c-9b3e-4a4573c9ba2d","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-cdd25856-ebc2-4f32-9ee7-0e92f1c0b40c [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-59716949-11b4-4303-9cfc-c4e32b144b1b","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-e9c4ccea-1f61-4f8a-9b3f-0c227717797b","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Check out its algorithm

Time complexity: O(n*sum) n- no of distinct coins, sum- desired sum. Space complexity: O(sum)

[{"selector":"#anim-4ec960fd-c651-4e6c-a06e-85d339bbf33f","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-fd7dfa93-652f-4e93-b9d3-4ffc2447f351","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-40f6b0e9-1eac-4445-a21b-d410e0a80d30 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] See code implementation

Want to explore these approaches and learn how to implement them in various programming languages?

[{"selector":"#anim-0ba830e7-8086-4084-b651-d452d45b05d5","keyframes":{"opacity":[0,1]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-44293ae2-6ebb-4803-9fc8-b2729963bf38","keyframes":{"transform":["translate3d(-112.4161%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-dc995e89-543a-4d45-a6df-c291bc31a3fc","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-2a2c7709-1b19-4f44-9b51-ae9cbc882b99","keyframes":{"transform":["translate3d(-109.375%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] SWIPE UP

How to Solve Coin Change Problem?

Let's dive in!

Given an array of coins and a total sum, find the fewest number of coins needed to make the sum. Return -1 if impossible.

Problem Statement

Example- Input: [1,2,5,9,8] Sum: 17 Output: 2 Explanation: Two coins require to make the desired sum [9,8]

Use recursion to check all possible combinations of coins to find the minimum number of coins needed to create the given sum. Update the number of coins needed with each iteration.

Simple Approach

Time complexity: Exponential. (every recursive call is making n recursive calls) Space complexity: O(1)

Solve the problem by breaking it down into smaller subproblems and using a bottom-up approach to compute dp[i] (1<=i<=subproblems) which stores the minimum number of coins needed to create the sum.

Efficient Approach: Dynamic Programming

Time complexity: O(n*sum) n- no of distinct coins, sum- desired sum. Space complexity: O(sum)

Want to explore these approaches and learn how to implement them in various programming languages?

Click on the link below to start your journey.