hackerrank-coin-change.c

//https://www.hackerrank.com/challenges/coin-change

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

int coins[55];
long sol[255];
int m;

int comp (const void * elem1, const void * elem2) {
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}

void sort_coins() {
    qsort (coins, m, sizeof(*coins), comp);
}

long solve(int n) {
    for (int j = 0; j < m; ++j) {
        int coin_value = coins[j];
        sol[coin_value]++;
        for (int i = 0; i <= n; ++i) {
            int x = i - coin_value;
            if (x > 0) {
                sol[i] += sol[x];
            }
        }
    }
    return sol[n];
}

int main() {
    int n;
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &coins[i]);
    }
    sort_coins();
    printf("%ld\n", solve(n));
    return 0;
}