Coin Change Min

AlgorithmAlgorithmBeginner
Practice Now

This tutorial is from open-source community. Access the source code

Introduction

In this Python challenge, we will be solving the problem of determining the minimum number of ways to make n cents, given coins of denominations less than n cents.


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python(("`Python`")) -.-> python/PythonStandardLibraryGroup(["`Python Standard Library`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/recursion_dynamic("`Recursion Dynamic`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/break_continue("`Break and Continue`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ModulesandPackagesGroup -.-> python/importing_modules("`Importing Modules`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/PythonStandardLibraryGroup -.-> python/os_system("`Operating System and System`") subgraph Lab Skills algorithm/recursion_dynamic -.-> lab-268854{{"`Coin Change Min`"}} python/conditional_statements -.-> lab-268854{{"`Coin Change Min`"}} python/for_loops -.-> lab-268854{{"`Coin Change Min`"}} python/break_continue -.-> lab-268854{{"`Coin Change Min`"}} python/lists -.-> lab-268854{{"`Coin Change Min`"}} python/tuples -.-> lab-268854{{"`Coin Change Min`"}} python/function_definition -.-> lab-268854{{"`Coin Change Min`"}} python/importing_modules -.-> lab-268854{{"`Coin Change Min`"}} python/standard_libraries -.-> lab-268854{{"`Coin Change Min`"}} python/classes_objects -.-> lab-268854{{"`Coin Change Min`"}} python/encapsulation -.-> lab-268854{{"`Coin Change Min`"}} python/raising_exceptions -.-> lab-268854{{"`Coin Change Min`"}} python/os_system -.-> lab-268854{{"`Coin Change Min`"}} end

Coin Change Min

Problem

Given a set of coins with denominations less than n cents, we need to determine the minimum number of ways to make n cents using these coins. The coins can be used in any combination and we have an infinite number of coins of each denomination. We do not need to report the combination(s) of coins that represent the minimum.

Requirements

To solve this problem, we need to consider the following requirements:

  • The coins have to reach exactly n cents.
  • We can assume we have an infinite number of coins to make n cents.
  • We do not need to report the combination(s) of coins that represent the minimum.
  • We cannot assume the coin denominations are given in sorted order.
  • We can assume this fits memory.

Example Usage

Here are some examples of how this function can be used:

  • coins: None or n: None -> Exception
  • coins: [] or n: 0 -> 0
  • coins: [1, 2, 3] or [3, 2, 1] -> 2

Summary

In this Python challenge, we have learned how to determine the minimum number of ways to make n cents using a set of coins with denominations less than n cents. We have also identified the requirements for solving this problem and provided some examples of how this function can be used.

Other Algorithm Tutorials you may like