Given a number N and two arrays arr1[] and arr2[] of length 4. The array arr1[] denotes the denomination of 1, 5, 10, and 20 and arr2[] denotes the count of denominations of 1, 5, 10, and 20 respectively. The task is to find the number of ways in which we can sum them up to a total of N with a limited number of denominations.
Examples:Â
Input: arr1[] = {1, 5, 10, 20}, arr2[] = {6, 4, 3, 5}, N = 123Â
Output: 5Â
Explanation:Â
There are 5 ways to sum up to 123 with the given denomination of coins.
Input: arr1[] = {1, 5, 10, 20}, arr2[] = {1, 3, 2, 1}, N = 50Â
Output: 1Â
Explanation:Â
There is only 1 way to sum up to 50 with the given denomination of coins.Â
Â
Naive Approach: Let the count of denominations be represented by A, B, C, and D. The naive approach is to run nested loops. Each loop will refer to the number of coins of each denomination. Find the number of coins of each denomination required to make N by the equation:Â
(a * 1) + (b * 5) + (c * 10) + (d * 20)) == NÂ
where 0 <= a <= A, 0 &<= b <= B, 0 <= c <= C, 0 <= d <= D and N is the total amount.Â
Â
Time Complexity: O(N4)Â
Auxiliary Space: O(1)Â
Better Approach: We can optimize the above naive approach by adding some extra bounds to the loops which will reduce some computations. By observing, we can easily reduce the complexity by discarding one loop by removing coin with denomination 1 from N and check if the below inequality holds true or not:Â Â
(N – A) <= (b * 5 + c * 10 + d * 20) <= N Â
Below is the implementation of the above approach:Â
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsint calculateWays(int arr1[], int arr2[],                  int N){    // Store the count of denominations    int A = arr2[0], B = arr2[1];    int C = arr2[2], D = arr2[3];Â
    // Stores the final result    int ans = 0;Â
    // As one of the denominations is    // rupee 1, so we can reduce the    // computation by checking the    // equality for N-(A*1) = N-A    for (int b = 0;         b <= B && b * 5 <= (N); b++)Â
        for (int c = 0;             c <= C             && b * 5 + c * 10 <= (N);             c++)Â
            for (int d = 0;                 d <= D                 && b * 5 + c * 10 + d * 20 <= (N);                 d++)Â
                if ((b * 5) + (c * 10)                        + (d * 20)                    >= (N - A))Â
                    // Increment the count                    // for number of ways                    ans++;    return ans;}Â
// Driver Codeint main(){    // Given Denominations    int N = 123;Â
    int arr1[] = { 1, 5, 10, 20 };    int arr2[] = { 6, 4, 3, 5 };Â
    // Function Call    cout << calculateWays(arr1, arr2, N);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsstatic int calculateWays(int arr1[], int arr2[],                         int N){         // Store the count of denominations    int A = arr2[0], B = arr2[1];    int C = arr2[2], D = arr2[3];Â
    // Stores the final result    int ans = 0;Â
    // As one of the denominations is    // rupee 1, so we can reduce the    // computation by checking the    // equality for N-(A*1) = N-A    for(int b = 0;            b <= B && b * 5 <= (N); b++)                     for(int c = 0;                c <= C && b * 5 + c * 10 <= (N);                c++)Â
            for(int d = 0;                    d <= D &&                     b * 5 + c * 10 + d * 20 <= (N);                    d++)Â
                if ((b * 5) + (c * 10) +                    (d * 20) >= (N - A))Â
                    // Increment the count                    // for number of ways                    ans++;    return ans;}Â
// Driver Codepublic static void main(String[] args){         // Given denominations    int N = 123;Â
    int arr1[] = { 1, 5, 10, 20 };    int arr2[] = { 6, 4, 3, 5 };Â
    // Function call    System.out.print(calculateWays(arr1, arr2, N));}}Â
// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program for the above approachÂ
# Function to find the number of# ways to sum up a total of N# from limited denominationsdef calculateWays(arr1, arr2, N):       # Store the count of denominations    A = arr2[0]    B = arr2[1]    C = arr2[2]    D = arr2[3]Â
    # Stores the final result    ans, b, c, d = 0, 0, 0, 0Â
    # As one of the denominations is    # rupee 1, so we can reduce the    # computation by checking the    # equality for N-(A*1) = N-A    while b <= B and b * 5 <= (N):        c = 0Â
        while (c <= C and               b * 5 + c * 10 <= (N)):            d = 0Â
            while (d <= D and                   b * 5 + c * 10 +                   d * 20 <= (N)):                               if ((b * 5) + (c * 10) +                    (d * 20) >= (N - A)):Â
                    # Increment the count                    # for number of ways                    ans += 1                d += 1            c += 1        b += 1             return ans   # Driver Codeif __name__ == '__main__':       # Given Denominations    N = 123Â
    arr1 = [ 1, 5, 10, 20 ]    arr2 = [ 6, 4, 3, 5 ]Â
    # Function Call    print(calculateWays(arr1, arr2, N))Â
# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;Â
class GFG{Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsstatic int calculateWays(int []arr1, int []arr2,                         int N){         // Store the count of denominations    int A = arr2[0], B = arr2[1];    int C = arr2[2], D = arr2[3];Â
    // Stores the readonly result    int ans = 0;Â
    // As one of the denominations is    // rupee 1, so we can reduce the    // computation by checking the    // equality for N-(A*1) = N-A    for(int b = 0;            b <= B && b * 5 <= (N); b++)                     for(int c = 0;                c <= C && b * 5 + c * 10 <= (N);                c++)Â
            for(int d = 0;                    d <= D &&                     b * 5 + c * 10 + d * 20 <= (N);                    d++)Â
                if ((b * 5) + (c * 10) +                    (d * 20) >= (N - A))Â
                    // Increment the count                    // for number of ways                    ans++;                         return ans;}Â
// Driver Codepublic static void Main(String[] args){         // Given denominations    int N = 123;Â
    int []arr1 = { 1, 5, 10, 20 };    int []arr2 = { 6, 4, 3, 5 };Â
    // Function call    Console.Write(calculateWays(arr1, arr2, N));}}Â
// This code is contributed by PrinciRaj1992 |
Javascript
<script>Â
// Javascript program for the above approach  // Function to find the number of// ways to sum up a total of N// from limited denominationsfunction calculateWays(arr1, arr2,                         N){          // Store the count of denominations    let A = arr2[0], B = arr2[1];    let C = arr2[2], D = arr2[3];      // Stores the final result    let ans = 0;      // As one of the denominations is    // rupee 1, so we can reduce the    // computation by checking the    // equality for N-(A*1) = N-A    for(let b = 0;            b <= B && b * 5 <= (N); b++)                      for(let c = 0;                c <= C && b * 5 + c * 10 <= (N);                c++)              for(let d = 0;                    d <= D &&                    b * 5 + c * 10 + d * 20 <= (N);                    d++)                  if ((b * 5) + (c * 10) +                    (d * 20) >= (N - A))                      // Increment the count                    // for number of ways                    ans++;    return ans;}Â
// Driver CodeÂ
     // Given denominations    let N = 123;      let arr1 = [ 1, 5, 10, 20 ];    let arr2 = [ 6, 4, 3, 5 ];      // Function call    document.write(calculateWays(arr1, arr2, N));Â
</script> |
5
Â
Time Complexity: O(N3)Â
Auxiliary Space: O(1)
Efficient Approach: Let the count of denominations be represented by A, B, C, and D. The efficient approach for solving the above problem is to count the possible number of denominations formed using C and D. Then we will find the remaining value with denominations of A and B. Below are the steps:
- Initialize the array ways[] to store the precomputed sum of denominations of A and B.
- Iterate two nested loops to store the combination of values formed by denominations of A and B in ways[].
- Iterate two nested loops to find all the combinations of values formed by denominations of C and D and add all the possible combinations of the value N – (C*10 + D*20), which is equivalent to (A * 1) + (B * 5).
- The sum of all values in the above step is the required result.
Below is the implementation of the above approach:Â
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int ways[1010];Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsint calculateWays(int arr1[], int arr2[],                  int N){    // Store the count of denominations    int A = arr2[0], B = arr2[1];    int C = arr2[2], D = arr2[3];Â
    // Stores the final result    int ans = 0;Â
    // L1 : Incrementing the values    // with indices with denomination    // (a * 1 + b * 5)Â
    // This will give the number of coins    // for all combinations of coins    // with value 1 and 5    for (int b = 0;         b <= B && b * 5 <= N; b++) {Â
        for (int a = 0;             a <= A             && a * 1 + b * 5 <= N;             a++) {            ways[a + b * 5]++;        }    }Â
    // L2 will sum the values of those    // indices of ways[] which is equal    // to (N - (c * 10 + d * 20))    for (int c = 0;         c <= C && c * 10 <= (N); c++) {Â
        for (int d = 0;             d <= D             && c * 10 + d * 20 <= (N);             d++) {            ans += ways[N - c * 10 - d * 20];        }    }Â
    // Return the final count    return ans;}Â
// Driver Codeint main(){    // Given Denominations    int N = 123;Â
    int arr1[] = { 1, 5, 10, 20 };    int arr2[] = { 6, 4, 3, 5 };Â
    // Function Call    cout << calculateWays(arr1, arr2, N);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â Â Â Â Â static int []ways = new int[1010];Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsstatic int calculateWays(int arr1[], int arr2[],                         int N){         // Store the count of denominations    int A = arr2[0], B = arr2[1];    int C = arr2[2], D = arr2[3];Â
    // Stores the final result    int ans = 0;Â
    // L1 : Incrementing the values    // with indices with denomination    // (a * 1 + b * 5)Â
    // This will give the number of coins    // for all combinations of coins    // with value 1 and 5    for(int b = 0;             b <= B && b * 5 <= N; b++)     {        for(int a = 0;                 a <= A && a * 1 + b * 5 <= N;                a++)         {            ways[a + b * 5]++;        }    }Â
    // L2 will sum the values of those    // indices of ways[] which is equal    // to (N - (c * 10 + d * 20))    for(int c = 0;             c <= C && c * 10 <= (N); c++)     {        for(int d = 0;                 d <= D && c * 10 + d * 20 <= (N);                d++)         {            ans += ways[N - c * 10 - d * 20];        }    }Â
    // Return the final count    return ans;}Â
// Driver Codepublic static void main(String[] args){         // Given denominations    int N = 123;Â
    int arr1[] = { 1, 5, 10, 20 };    int arr2[] = { 6, 4, 3, 5 };Â
    // Function call    System.out.print(calculateWays(arr1, arr2, N));}}Â
// This code is contributed by Princi Singh |
Python3
# Python3 program for # the above approachways = [0 for i in range(1010)];Â
# Function to find the number of# ways to sum up a total of N# from limited denominationsdef calculateWays(arr1, arr2, N):Â
    # Store the count of denominations    A = arr2[0]; B = arr2[1];    C = arr2[2]; D = arr2[3];Â
    # Stores the final result    ans = 0;Â
    # L1 : Incrementing the values    # with indices with denomination    # (a * 1 + b * 5)Â
    # This will give the number of coins    # for all combinations of coins    # with value 1 and 5    for b in range(0, B + 1):        if(b * 5 > N):            break;        for a in range(0, A + 1):            if(a + b * 5 > N):                break;            ways[a + b * 5] += 5;   Â
    # L2 will sum the values of those    # indices of ways which is equal    # to (N - (c * 10 + d * 20))    for c in range(0, C):        if(c * 10 > N):            break;        for d in range(0, D):            if(c * 10 + d * 20 > N):                break;            ans += ways[N - c * 10 - d * 20];   Â
    # Return the final count    return ans;Â
# Driver Codeif __name__ == '__main__':Â
    # Given denominations    N = 123;Â
    arr1 = [1, 5, 10, 20];    arr2 = [6, 4, 3, 5];Â
    # Function call    print(calculateWays(arr1, arr2, N));Â
# This code is contributed by gauravrajput1 |
C#
// C# program for the above approachusing System;Â
class GFG{Â Â Â Â Â static int []ways = new int[1010];Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsstatic int calculateWays(int []arr1, int []arr2,                         int N){         // Store the count of denominations    int A = arr2[0], B = arr2[1];    int C = arr2[2], D = arr2[3];Â
    // Stores the readonly result    int ans = 0;Â
    // L1 : Incrementing the values    // with indices with denomination    // (a * 1 + b * 5)Â
    // This will give the number of coins    // for all combinations of coins    // with value 1 and 5    for(int b = 0;             b <= B && b * 5 <= N; b++)     {        for(int a = 0;                 a <= A && a * 1 + b * 5 <= N;                a++)         {            ways[a + b * 5]++;        }    }Â
    // L2 will sum the values of those    // indices of ways[] which is equal    // to (N - (c * 10 + d * 20))    for(int c = 0;             c <= C && c * 10 <= (N); c++)     {        for(int d = 0;                 d <= D && c * 10 + d * 20 <= (N);                d++)         {            ans += ways[N - c * 10 - d * 20];        }    }Â
    // Return the final count    return ans;}Â
// Driver Codepublic static void Main(String[] args){         // Given denominations    int N = 123;Â
    int []arr1 = { 1, 5, 10, 20 };    int []arr2 = { 6, 4, 3, 5 };Â
    // Function call    Console.Write(calculateWays(arr1, arr2, N));}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>Â
// Javascript program for the above approachvar ways = Array(1010).fill(0);Â
// Function to find the number of// ways to sum up a total of N// from limited denominationsfunction calculateWays(arr1, arr2, N){    // Store the count of denominations    var A = arr2[0], B = arr2[1];    var C = arr2[2], D = arr2[3];Â
    // Stores the final result    var ans = 0;Â
    // L1 : Incrementing the values    // with indices with denomination    // (a * 1 + b * 5)Â
    // This will give the number of coins    // for all combinations of coins    // with value 1 and 5    for (var b = 0;         b <= B && b * 5 <= N; b++) {Â
        for (var a = 0;             a <= A             && a * 1 + b * 5 <= N;             a++) {            ways[a + b * 5]++;        }    }Â
    // L2 will sum the values of those    // indices of ways[] which is equal    // to (N - (c * 10 + d * 20))    for (var c = 0;         c <= C && c * 10 <= (N); c++) {Â
        for (var d = 0;             d <= D             && c * 10 + d * 20 <= (N);             d++) {            ans += ways[N - c * 10 - d * 20];        }    }Â
    // Return the final count    return ans;}Â
// Driver CodeÂ
// Given Denominationsvar N = 123;var arr1 = [1, 5, 10, 20];var arr2 = [6, 4, 3, 5];Â
// Function Calldocument.write( calculateWays(arr1, arr2, N));Â
Â
</script> |
5
Â
Time Complexity: O(N2)Â
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
