Number of ways of representing n cents using quarters, dimes, nickels and pennies

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

My initial thoughts:

  • Base case: n < 0. No way to do it.
  • Recursion: Represent n by using 1 quarter if possible + # ways of representing (n-25) cents. Or, Represent n by using 1 nickel if possible + # ways of representing (n-10) cents. Or, Represent n by using 1 nickels if possible + # ways of representing (n-5) cents. And we always have 1 way to represent n cents using n pennies.

My initial codes:

	public static int waysOfRepresentingNCents(int n) {
		if (n < 0)
			return 0;
		else {
			int ways = 0;
			if (n >= 25)
				ways += waysOfRepresentingNCents(n - 25);
			if (n >= 10)
				ways += waysOfRepresentingNCents(n - 10);
			if (n >= 5)
				ways += waysOfRepresentingNCents(n - 5);
			ways += 1;
			return ways;
		}
	}

Comments after running:
Logic error.

  • INPUT: n = 15.
  • EXPECTED OUTPUT: 6 ways of representing 15 cents
  • ACTUAL OUTPUT: 7.
  • PROBLEM: Duplicate counting: 10 + 5 and 5 + 10 are the same way of representing 15 cents but they are counted twice. So we should have ordering.

Solution:

	public static int makeChange(int n, int denom) {
		int next_denom = 0;
		switch (denom) {
		case 25:
			next_denom = 10;
			break;
		case 10:
			next_denom = 5;
			break;
		case 5:
			next_denom = 1;
			break;
		case 1:
			return 1;
		}
		int ways = 0;
		for (int i = 0; i * denom <= n; i++) {
			ways += makeChange(n - i * denom, next_denom);
		}
		return ways;
	}
Advertisements

2 Comments (+add yours?)

  1. sophie
    Oct 20, 2013 @ 19:29:00

    Hey Runhe, do u know the time complexity of the solution? Thanks !

    Reply

  2. Anonymous
    Jul 16, 2014 @ 20:28:33

    You did not explain how you got to second solution after finding out error that duplicate counting is made in first solution

    Reply

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: