Modified Coin Change

November 19, 2019

This is a trick question.

In the general coin change problem, dynamic programming is required because the greedy algorithm doesn’t work for some sets of coins. But with the coins restricted to powers of 5, the greedy algorithm does work. And, in fact, there is an even simpler algorithm; express the number in base 5 and sum its digits:

(define (f n) (sum (digits n 5)))
> (f 42)
6
> (f 142)
6

 

That’s 25+5+5+5+1+1 for the first problem, and 125+5+5+5+1+1 for the second problem. You can run the program at https://ideone.com/bgOJvY.

Pages: 1 2

2 Responses to “Modified Coin Change”

  1. Daniel said

    Here’s a solution in Python.

    def modified_cc(n):
        out = 0
        while n > 0:
            n, r = divmod(n, 5)
            out += r
        return out
    
    print(modified_cc(42))
    print(modified_cc(142))
    

    Output:

    6
    6
    
  2. Daniel said

    Here’s a solution in C that’s similar to the Python solution I posted earlier.

    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    int modified_cc(int n) {
      int out = 0;
      while (n > 0) {
        out += n % 5;
        n /= 5;
      }
      return out;
    }
    
    int main(int argc, char* argv[]) {
      assert(argc == 2);
      int n = atoi(argv[1]);
      printf("%d\n", modified_cc(n));
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./a.out 42
    6
    
    $ ./a.out 142
    6
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: