Ways To Make Coin Change

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

Input Format
The first line of input contains an integer N, representing the total number of denominations.

The second line of input contains N integers values separated by a single space. Each integer value represents the denomination value.

The third line of input contains the value of V, representing the value for which the change needs to be generated.
Output Format:
For each test case, print an integer denoting the total number of ways W, in which a change for V is possible.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= N <= 10
1 <= D[i] <=10^5
1 <= V <= 2 * 10^3

Where 'D[i]' represent the value of ith denomination. 

Time Limit: 1sec
CodingNinjas
author
2y
Recursion

  1. The idea is to use recursion.
  2. For a particular coin, we have two options either include it or exclude it.
  3. If we include that coin, then calculate the remaining number that we have to generate ...read more
CodingNinjas
author
2y
Recursion And Memoization
  1. The idea is to use recursion and memoization. So first create a 2D array 'memo' that will store the answer of all subproblems that we compute.
  2. For a particular coin, if the ans...read more
CodingNinjas
author
2y
Iterative DP
  1. The idea is to use dynamic programming.
  2. Create a two-dimensional array, ‘ways’, where ‘ways[i][j]’ will denote the total number of ways to make j value by using i coins.
  3. Fill dp array by the...read more
CodingNinjas
author
2y
Space Optimised Iterative Approach
  1. The idea is to use dynamic programming
  2. As by recurrence relation of previous approach, we can easily see that it is only dependent on previous row, so we can optimise ...read more
Add answer anonymously...
Standard Chartered Full Stack Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions
Get AmbitionBox app

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter