DAA Lab DA 2 PP 2.1 Q1

#include <stdio.h>
#include <stdlib.h>

void sortDesc(int arr[], int n){
    int i, j, t;
    for(i = 0; i < n-1; i++){
        for(j = i+1; j < n; j++){
            if (arr[i] < arr[j]){
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
    }
}

int coinsUsed(int m, int d[], int n, int used[]){
    if (m <= 0){
        return 0;
    }
    int i;
    for (i = 0; i < n; i++){
        if (m >= d[i]){
            used[i]++;
            return 1 + coinsUsed(m-d[i], d, n, used);
        }
    }
}


void solve(){
    // input
    int m;
    int n;
    printf("Enter the amount M: ");
    scanf("%d", &m);
    printf("\nEnter the number of denomination: ");
    scanf("%d", &n);
    int* d = (int*)malloc(sizeof(int) * n);
    int* used = (int*)malloc(sizeof(int) * n);
    int i;
    printf("\nEnter the denominations: ");
    for(i = 0; i < n; i++){
        scanf("%d", &d[i]);
        used[i] = 0;
    }

    // sort the denominations in descending order
    sortDesc(d, n);

    // solving using recursive greedy algo
    int c = coinsUsed(m, d, n, used);

    printf("\nTotal coins = %d (", c);
    for(i = 0; i < n-1; i++){
        while(used[i] > 0){
            printf(" %d ", d[i]);
            used[i]--;
        }
    }
    printf(")");
}

int main(){
    solve();
    return 0;
}