Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Coin exchange problem solution Implementation in Java

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 990
    Comment on it

    Hi, In this blog I tried to provide an efficient solution for a famous coin exchange problem using dynamic problem in bottom up approach whose time complexity is O(mn).

    Problem Definition

    In coin exchange problem you can think of a coin vending machine of a Bank having abundant supply of coins which returns back coins in exchange to the note put into it by the people, In that case machine will return coins, sum of which will amount the same value put into the machine, here order doesn't matter ( i.e. {1,2,2} ,{2,1,2}, {2,2,1} will be consider as same ).
    Now the problem is that, you have to find the total number of solution in which you can perform this operation.

    For example : 

    Suppose the machine has infinite supply of 1, 2, 3 rupees coins.
    One person came and want exchange for a 5 rupees note. 
    Now machine can return his money in form of 
    {1,1,1,1,1} rupees coin 
    {1,1,1,2}    rupees coin
    {1,2,2}       rupees coin
    {5}             rupees coin

    so there are 4 ways to do this.

    You can read more about this problem here https://en.wikipedia.org/wiki/Change-making_problem

    Java solution for the above problem using bottom up approach

    package com.tech.blog;
    
    import java.util.Scanner;
    
    public class CoinExchangeProblem {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n;
    		int x;
    		int y;
    		int sum;
    
    		//Final sum of the value in return of which coins are being given 
    		System.out.print("Enter the final sum to be formed using coins : ");
    		sum = sc.nextInt();
    
    		//For the count of set of coins ( count of different values of coins )
    		System.out.print("Enter total number of coins : ");
    		n = sc.nextInt();
    		
    		int[] coin = new int[n];
    
    		// To input the values of coins for our problem
    		System.out.print("Enter values of coins : ");
    		for (int i = 0; i < n; i++)
    			coin[i] = sc.nextInt();
    		sc.close();
    
    		// We need sum + 1 rows as the table is constructed in bottom up manner using 
    	    // the base case 0 value case (n = 0)
    		int[][] solution = new int[sum + 1][n];
    		
    		//Base case fill all the entries for 0 value case (n = 0)
    		for (int i = 0; i < n; i++)
    			solution[0][i] = 1;
    		
    		// Filling the table entries in bottom up manner
    		for (int i = 1; i < sum + 1; i++) {
    			for (int j = 0; j < n; j++) {
    				// number of solutions including coin[j]
    				x = (i - coin[j] >= 0) ? solution[i - coin[j]][j] : 0;
    
    				// number of solutions excluding coin[j]
    				y = (j >= 1) ? solution[i][j - 1] : 0;
    
    				// total number of solution
    				solution[i][j] = x + y;
    			}
    		}
    		System.out.println("Total solutions for your problem is "
    				+ solution[sum][n - 1]);
    		return;
    	}
    }
    

     

    Output of the above code

    Enter the final sum to be formed using coins :4
    Enter total number of coins :3
    Enter values of coins :123
    Total solutions for your problem is 4

     

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: