Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [coin-change]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
113 views

Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
user avatar
2 votes
1 answer
2k views

Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
user avatar
2 votes
3 answers
455 views

Algorithm for fewest number of moves with artificial minimum

I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum. To summarize, I built an undirected graph with edges ...
user avatar
1 vote
1 answer
936 views

dynamic pseudo-code for simplified coin changing algorithm

As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible ...
user avatar
1 vote
1 answer
2k views

What Are the Ideas Behind Variations of the Coin Change Problem?

Problem: given a set of n coins of unique face values, and a value change, find number of ways of making change for ...
user avatar
3 votes
2 answers
2k views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
user avatar
1 vote
1 answer
104 views

"Ways to make change for a dollar": How to optimize with constraints

I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
user avatar
  • 113
2 votes
1 answer
1k views

Solving "coin exchange" for coins of power values by greedy algorithm

When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$? For ...
user avatar
0 votes
1 answer
423 views

Coin Change Problem Recurrence Relation with one parameter

I have been looking through the recursive formulation for the coin change problem here and am wondering if it is possible to define the function $ C(N, m) $ in one parameter as $C(N)$, therefore not ...
user avatar
1 vote
0 answers
90 views

Reducing Coin Change Problem running time to depend on the denominations, not sum being changed

I asked my Advanced Algorithms professor recently if we could solve the coin change problem (least number of coins necessary to make change for S cents using denominations d1, d2, ... dk). I thought ...
user avatar
0 votes
0 answers
364 views

Space complexity of Coin change with memoization

I've read conflicting answers for the space complexity of the top down implementation w/ memoization for the classic coin change problem. Would this be O(N * M) space as Interview Cake says https://...
user avatar
  • 101
2 votes
3 answers
4k views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
user avatar
1 vote
0 answers
36 views

Is this solution is bad for the coin change problem? [closed]

was doing coin change problem as an assignment(didnt know before), after came with this solution i checked the solutions available couldnt find a similar one like this, just curious. removing the ...
user avatar
  • 111
1 vote
0 answers
133 views

Does an algorithm exist for solving the change-making problem using a finite coin library of known size?

I'm currently working on implementing an algorithm to solve a real-world problem I'm encountering in a lab, but with little background in algorithms, I'm struggling to create an ideal solution. I ...
user avatar
1 vote
2 answers
1k views

Printing actual solutions for the coin exchange problem

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight ...
user avatar
2 votes
1 answer
1k views

Dynamic Programming for a variant of the coin exchange problem

I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem: Given a value N, if we want to make change for N cents, and we have ...
user avatar
0 votes
0 answers
271 views

Implementing supplies in Coin change problem

I started an algorithm course in C two months ago, for the last weeks I've been trying to solve this problem , i ran out of time but I cannot find an acceptable solution. Basically It's a coin change ...
user avatar
  • 1
7 votes
1 answer
5k views

Analyzing time complexity for change making algorithm (Brute force)

I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so: Since the tree can have a maximum height of 'n' and at every ...
user avatar
  • 173
5 votes
2 answers
825 views

Can counting problems have optimal substructure?

I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties: optimal substructure overlapping subproblems I stumbled upon an article which ...
user avatar
  • 220
3 votes
1 answer
5k views

Recurrence relation of the coin change problem

I'm trying to wrap my head around the coin change problem, where you try to find the total number of ways $N$ cents can be exchanged using $M$ coins $\{C_1, C_2, ..., C_m\}$. The recurrence relation ...
user avatar
  • 204
2 votes
2 answers
2k views

What are applications of Coin Change problem?

I've read so many about the Coin Change problem, debates about wheather it is solvable using Greedy, Dynamic Programming and so on. Nevertheless I cannot find an application of this problem. What ...
user avatar
  • 854
2 votes
3 answers
812 views

Coin Change Problem(Greedy Algorithm)

In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm? Example- $(1,3,4)$ are denominations of coin. If I want to pay ...
user avatar
2 votes
1 answer
2k views

A variant of coin change problem

Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in ...
user avatar
  • 329