OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

Coin Change II : To take a value or not to

  • Thread starter Thread starter ABGR
  • Start date Start date
A

ABGR

Guest
The problem goes like this:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

Here's how I thought to take on this problem: On any given index here're three things I can do:

  • I take the value of the index and remain at the same index
  • I take the value of the index and move on to the next one
  • I do not take the value of the index and move on to the next one.

Now obviously I got the answer wrong.


Code:
var change = function(amount, coins, index = 0) {
    if(amount === 0) return 1;
    if(index >= coins.length|| amount < 0)  return 0;

    let way1 = change(amount - coins[index], coins, index);
    let way2 = change(amount - coins[index], coins, index+1);
    let way3 = change(amount, coins, index+1);

    return way1 + way2 + way3;

};

console.log(change(3, [1,2,5]))

So I debugged and found the reason. The second step is just adding extra number of ways.

And hence I removed and got the solution accepted.


Code:
var change = function(amount, coins, index = 0, memo={}) {
    if((amount+','+index) in memo) return memo[amount+','+index];
    if(amount === 0) return 1;
    if(index >= coins.length|| amount < 0)  return 0;

    let way1 = change(amount - coins[index], coins, index, memo);
    let way2 = change(amount, coins, index+1, memo);

    memo[amount+','+index] = way1 + way2;
    return memo[amount+','+index];

};

console.log(change(5, [1,2,5]))

Now somehow I'm unable to logically think why way2 was un-necessary. After all, it makes logically sense to take the value at that index and still move to the other one. Appreciate thoughts on this.

<p>The problem goes like this:</p>
<p>You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.</p>
<p>Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.</p>
<p>You may assume that you have an infinite number of each kind of coin.</p>
<p>Here's how I thought to take on this problem:
On any given index here're three things I can do:</p>
<ul>
<li>I take the value of the index and remain at the same index</li>
<li>I take the value of the index and move on to the next one</li>
<li>I do not take the value of the index and move on to the next one.</li>
</ul>
<p>Now obviously I got the answer wrong.</p>
<p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>var change = function(amount, coins, index = 0) {
if(amount === 0) return 1;
if(index >= coins.length|| amount < 0) return 0;

let way1 = change(amount - coins[index], coins, index);
let way2 = change(amount - coins[index], coins, index+1);
let way3 = change(amount, coins, index+1);

return way1 + way2 + way3;

};

console.log(change(3, [1,2,5]))</code></pre>
</div>
</div>
</p>
<p>So I debugged and found the reason. The <em>second step</em> is just adding extra number of ways.</p>
<p>And hence I removed and got the solution accepted.</p>
<p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>var change = function(amount, coins, index = 0, memo={}) {
if((amount+','+index) in memo) return memo[amount+','+index];
if(amount === 0) return 1;
if(index >= coins.length|| amount < 0) return 0;

let way1 = change(amount - coins[index], coins, index, memo);
let way2 = change(amount, coins, index+1, memo);

memo[amount+','+index] = way1 + way2;
return memo[amount+','+index];

};

console.log(change(5, [1,2,5]))</code></pre>
</div>
</div>
</p>
<p>Now somehow I'm unable to logically think why way2 was un-necessary. After all, it makes logically sense to take the value at that index and still move to the other one. Appreciate thoughts on this.</p>
 

Latest posts

S
Replies
0
Views
1
Sergey Bakaev Rettley
S
Top