The coin change problem is one of the popular coding interview question and knowing how to solve this problem can help you during coding interview. It's also useful to learn a couple of tricks and data structure. This problem somewhat has to do with arrays, so we shall be discussing what an array is, But before we dive into this. we need to understand the problem. We are about to solve a coin problem by determining how many possible ways an amount can be paid. Suppose, Mary is a Businesswoman who deals with coin change.

So a customer comes to change a particular amount of coin. So, with the coins Mary has, how many possible ways can she exchange the customers' coins. If Mary has the following coins 1,2,3,4,5 and the customer wants to change 16. The possible ways Mary could change the coin are:

Example 1 :

Input: [1,2,3,4,5]

Sum: 16

Output: 4

Explanation: Four coins require to make the desired sum which is [5,5,5,1]

Example 2:

input: [2, 4, 6, 8]

Sum: 15

Output: -1

Explanation: There is no combination present with sum 15.

Example 3:

Input: [1,2,5,9,8]

Sum: 17

Output: 2

Explanation: Two coins require to make the desired sum which is [9,8]

In this approach, we can use recursion to solve this as we have to iterate over all the possible combinations of coins that equal the given sum every time update the minimum no of coins needed to create this sum.

__How to solve Coin Change Problem in Java__

- public class Main
- {
- public static int count(int[] coins, int number, int target)
- {
- if (target == 0) {
- return 1;
- }
- if (target < 0 || number< 0) {
- return 0;
- }
- int first= count(coins, number, target - coins[number]);
- int second= count(coins, number - 1, target);
- return first + second;
- }
- public static void main(String[] args)
- {
- int[] coinArray = { 1, 2, 3 };
- int target = 4;
- System.out.print("The total number of ways to get the desired change is "
- + count(coinArray, coinArray.length - 1, target));
- }
- }

### HOW ARRAYS WORK

**CONCLUSION**

In this article, you learned how to solve a coin change problem. Also, remember that any attempt to add more than what you have specified in a particular array results in An Array index out-of-bounds Exception. You can't say the length of items coming in at creation is 10 and eventually, you put 11 items, Sorry it won't work!.

Other **Array and Coding Problems** you may like

- How to sort an array in place in Java? (solution)
- Top 5 Websites for Coding Interview Preparation (websites)
- 7 Best Courses to learn Data Structure and Algorithms? (courses)
- How to check if an array contains a particular value? (solution)
- Prime Number Generation Algorithms - Sieve of Eratosthenes (algorithm)
- How to remove an element from an array in Java? (solution)
- Top 20 String Coding Problems from Interviews (questions)
- How to find duplicates from an unsorted array in Java? (solution)
- How to remove duplicates from an array in Java? (solution)
- How to find one missing number in a sorted array? (solution)
- 10 Courses to Learn Data Structure and Algorithms for Interviews (courses)
- How to find the largest and smallest number in an array without sorting? (solution)
- 75 Programming Questions to Crack Any Coding Interview (list)
- Binary Search Algorithm without Recursion (algorithm)
- How to find all pairs in an array whose sum is equal to k (solution)
- 20+ Array-Based Coding Problems from interviews (questions)

Thanks for reading this article so far. If you like this array-based coding interview question about finding coin change and my solution and explanation then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

## No comments:

## Post a Comment

Feel free to comment, ask questions if you have any doubt.