[Solved] How to solve a coin change problem in Java? Example

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.

So, the purpose of this is to give you a background understanding of the problem. So I hope this helps

How to solve Coin Change Problem in Java

Now let us see the code implementation:

1. public class Main
2. {
3. public static int count(int[] coins, int number, int target)
4. {
5. if (target == 0) {
6. return 1;
7. }
8. if (target < 0 || number< 0) {
9. return 0;
10. }
11. int first= count(coins, number, target - coins[number]);
12. int second= count(coins, number - 1, target);
13. return first + second;
14. }
15.  
16. public static void main(String[] args)
17. {
18. int[] coinArray = { 1, 2, 3 };
19. int target = 4;
20. System.out.print("The total number of ways to get the desired change is "
21. + count(coinArray, coinArray.length - 1, target));
22. }
23. }

To explain the following code implementation, we have a method called count() in line 3, which takes in 3 parameters, firstly an array coin of type int, secondly a number of type int an as well a target of type it. (Target is that particular number we are looking out for). 

The first condition in line 4 says if the target is 0 then 1 should be returned. so the program ends from there but if not, it proceeds to the next line and checks the condition in line 8. which is, If the target is less than 0 or the number is less than 0 it should return 0. and ends there if the condition is true. 

But if the first and the second condition is false then it goes to line 11 and starts execution from there. This is a recursion call, a method calling itself in itself. 

 

So, the method was called twice and stored in two different variables, named first and second respectively. so the first method call took in coins, which is the array as the first argument, the second the argument is the number and the third argument is the target minus the coin array at the number i.e coin[number].

For the second method call, it took in the coins, the array, number - 1, and the target respectively. and it returned the sum of the first and second in line 13.

Line 16 is the main method. In line 18 a coin array was created and initialized with numbers.

Line 19 is the target variable of type int initialized to 4

Line 20 printed out the output of the method call and it was the appropriate argument: Coin array, its length - 1, and the target.

HOW ARRAYS WORK

An array is a collection of elements of the same value. This means that you can not find different kinds of elements or data types there. You can see above that we only have an array of integers, they are numbers. In java, when you are creating an array newly you must do two important things: 

Fig 1.0 Array of Numbers

Firstly, you must say the type of element coming in. whether it's an integer or a string or a Boolean etc. The good thing is that once you specified the data type that is coming you can not do otherwise. you cant declare an int array and now populate it with a string element, No!, it doesn't work that way. It leads to a compilation error.

 

Secondly, When declaring an array in java, you must say the length that's coming. And that too can never change.  below is how to declare an array:

int [] numbers= new int [10]; 

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.