Curious Coin-Counting Problem
Difficulty : Medium
Given an amount A, we want you to compute the number of ways in which you
can gather A rupees if you have an infinite supply of each of C =  {1, 3, 5} valued rupee coins.

Input:
First line contains T, the number of test-cases. This is followed by T lines, where each line consists of the amount A.

Output:
For each test case, print the number of ways in which A can be formed using an infinite supply of 1, 3 and 5 rupee coins.

Sample Input:
2
5
10

Sample Output:
3
7

Constraints
T < 100
N < 101

Explanation (for first test case):
A = 5
Ways this amount can be achieved: {1,1,1,1,1}, {1,1,3}, {5}
Hence, the answer is 3.

Input Code:

{

    // If n is 0 then there is 1 solution (do not include any coin)

    if (n == 0)

        return 1;

    

    // If n is less than 0 then no solution exists

    if (n < 0)

        return 0;

    // If there are no coins and n is greater than 0, then no solution exist

    if (m <=0 && n >= 1)

        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]

    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

}

// Driver program to test above function

int main()

{

    int i, j,n,a[1000];

    int arr[] = {1, 3, 5};

    int m = sizeof(arr)/sizeof(arr[0]);

    scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

for(i=0;i<n;i++)

{

printf("%d\n", count(arr, m,a[i]));

}

        

    return 0;

}

Source code 2

#include<stdio.h>
int count( int S[], int m, int n )
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    if (m <=0 && n >= 1)
        return 0;
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int main()
{
 int N;
 scanf("%d", &N);
    int arr[] = {1, 5, 10, 50};
    printf("%d\n", count(arr, 4, N));
    return 0;
}

Sample Test Cases

	Input	Output
Test Case 1	2 5 10	3 7
Test Case 2	100 84 87 78 16 94 36 87 93 50 22 63 28 91 60 64 27 41 27 73 37 12 69 68 30 83 31 63 24 68 36 30 3 23 59 70 68 94 57 12 43 30 74 22 20 85 38 99 25 16 71 14 27 92 81 57 74 63 71 97 82 6 26 85 28 37 6 47 30 14 58 25 96 83 46 15 68 35 65 44 51 88 9 77 79 89 85 4 52 55 100 33 61 77 69 40 13 27 87 95 40	261 279 227 14 323 55 279 317 99 23 152 35 304 139 156 33 69 33 200 57 9 180 175 40 255 42 152 27 175 55 40 2 25 134 185 175 323 126 9 75 40 205 23 20 267 60 357 29 14 190 11 33 310 244 126 205 152 190 343 249 4 31 267 35 57 4 88 40 11 130 29 337 255 85 13 175 52 161 78 103 285 6 221 232 291 267 2 106 118 364 47 143 221 180 66 10 33 279 330 66