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

int numOfCalls = 0;
int change(int* coins, int noOfCoins, int amount) {
  numOfCalls++;

  for (int i=0; i<noOfCoins; i++) {
    if (amount == coins[i]) {
      //There was a coin of the searched amount.
      return 1;
    }
  }

  int minCoins = INT_MAX;
  int n;
  for (int i=1; i<=amount/2; i++) {
    n = change(coins, noOfCoins, amount-i) + change(coins, noOfCoins, i);
    if (n < minCoins) {
      minCoins = n;
    }
  }
  return minCoins;

}

main(int argn, char** args) {
  int coins[] = {1, 5, 10, 20, 50, 100, 500, 1000};
  int noOfCoins = 8;

  printf("Det krävs %d mynt.\n", change(coins, noOfCoins, atoi(args[1])));
  printf("Det krävdes %d anrop\n", numOfCalls);
}