Just [[currentUser.getNumFreeQuestionsLeft()]] No more free questions left!

Upgrade Now

Imagine you landed a new job as a cashier...

Your quirky boss found out that you're a programmer and has a weird request about something they've been wondering for a long time.

Write a function that, given:

  1. an amount of money
  2. an array of coin denominations

computes the number of ways to make amount of money with coins of the available denominations.

Example: for amount=4 (4¢) and denominations=[1,2,3] (1¢, 2¢ and 3¢), your program would output 4—the number of ways to make 4¢ with those denominations:

  1. 1¢, 1¢, 1¢, 1¢
  2. 1¢, 1¢, 2¢
  3. 1¢, 3¢
  4. 2¢, 2¢

What if there's no way to make the amount with the denominations? Does your function have reasonable behavior?

We can do this in time and space, where n is the amount of money and m is the number of denominations.

A simple recursive approach works, but you'll find that your function gets called more than once with the same inputs. We can do better.

We could avoid the duplicate function calls by memoizing, but there's a cleaner bottom-up approach.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

time and additional space, where n is the amount of money and m is the number of potential denominations.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

What's next?

RUN
Code execution powered by Qualified.io

. . .