Ways To Make Coin Change

Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make the change, the result should be 0.

Input:

The first line contains an integer N, denoting the total number of denominations.
The second line contains N space-separated integers, each representing a denomination value.
The third line contains the integer V, representing the value to make change for.

Output:

An integer denoting the total number of ways to make change for V.

Example:

Input:
N = 3
D = [1, 2, 3]
V = 4
Output:
4
Explanation:

There are four ways to make change for 4 using the denominations [1, 2, 3]:
1. 1+1+1+1
2. 1+1+2
3. 1+3
4. 2+2

Constraints:

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

Note: You don't need to handle the output; just implement the function as specified.

Be the first one to answer
Add answer anonymously...
Tata CLiQ Software 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

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