1

Consider a collection of coins with denominations 1, 2, . . . , 2^k (2 to the power of k) for some fixed k ≥ 0. Assuming that you have an unlimited supply of coins of each value, describe an algorithm that makes change for a given integer value V using the least number of coins. Explain why your algorithm is correct.

Xlyon
  • 323
  • 1
    Isn't it just the expression of $V$ is base $2$? – lhf Nov 11 '15 at 10:51
  • Note that if two coins of the same value are used, they can be replaced with one coin of double value (except for $2^k$). Note that there is only one way to make change for given $V$ with no more than one coin of each value (except $2^k$). – Abstraction Nov 11 '15 at 10:53
  • @Abstraction there is no double value here. the number is 2 to the power of k. probably you can choose the highest 2^k first then find the next high and so on. I think – Xlyon Nov 11 '15 at 11:37
  • @lhf no because it could be any number. and you can't give back 2.6 coins let's say. you need a normal number of coins to be returned – Xlyon Nov 11 '15 at 11:38
  • The coins have denominations powers of $2$ or all consecutive denominations from $1$ to $2^k$? – lhf Nov 11 '15 at 11:57
  • @lhf 1, 2, 8, 16, 32, 64, 128, 256, .... meaning 2^k where k >= 0. note: when k=0 that means 2^k=1 – Xlyon Nov 11 '15 at 12:10
  • @Xlyon In other words: two coins of value $2^n$ can be replaced with one coin of value $2^{n+1}$, unless $n=k$. There is one and only one way to pay sum $V$ using no more than one coin of value $2^n$ for all $n<k$. For $V<2^{k+1}$ Ihf gave correct answer, I have no idea where you got 2.6 coins. – Abstraction Nov 11 '15 at 12:29
  • @Abstraction I understood his and your answer. there can't be two coins of value 2^n anyway. let's say V=270. coins will be 256 + 8 + 2 + 2 + 2. That is 5 coins. your answers did not help the problem. – Xlyon Nov 11 '15 at 12:44
  • 1
    @Xlyon 270 = 256+8+4+2, that's 4 coins (for $k \ge 8$). Isn't it? – Abstraction Nov 11 '15 at 12:47
  • @Abstraction Yes exactly. I forgot the 4. So now all we need is the algorithm to how did this happen. – Xlyon Nov 11 '15 at 12:48

4 Answers4

2

If $V=2W$ is even, then find the representation of $W$ and shift all coins to the next denomination.

If $V=2W+1$ is odd, then find the representation of $2W$ and above and add a $1$ cent coin.

Since you can recover the representation of $W$ from the representation of $V$, by induction this recursive algorithm gives the best possible representation.

This is the same as finding the representation of $V$ in base $2$, except that you're limited to a finite number of denominations and so cannot shift the largest denomination. For $V<2^{k+1}$, you can use at most one coin of each denomination. For $V\ge2^{k+1}$, you may need to repeat the largest coin: $$43=1+42=1+2[21]=1+2[1+2[10]]=1+2[1+2[8+2]]=1+2[1+2\cdot8+4]\\=1+2+4\cdot8+8=1+2+5\cdot8$$

So the algorithm can be simplified to: remove the largest multiple of $2^k$ from $V$ and express $V-n2^k$ in binary.

lhf
  • 216,483
  • See also http://math.stackexchange.com/questions/1331354/proving-binary-integers. – lhf Nov 11 '15 at 12:56
1

In C#:

// Use: PrintChange(270,8);
void PrintChange(int V, int k, int coinValue = 1){
  if(k==0) Console.WriteLine("Coins of value " + coinValue + " - " + V);
  if(V%2==1) Console.WriteLine("Coins of value " + coinValue + " - 1");
  return PrintChange(V/2, k-1, coinValue*2);
}
Abstraction
  • 2,482
  • but when I divide 270/2=135. how can you call the function Printchange again when it is dividing this value/2 again? – Xlyon Nov 11 '15 at 13:21
  • 1
    @Xlyon In C-like languages a/b for integral a and b is actually $\lfloor{a \over b}\rfloor$, so 135/2=67. – Abstraction Nov 11 '15 at 13:35
0

In C++

vector<int> changeBinary(int input)
{
    vector<int> result;
    int index = 0;
    while (input != 0) 
    {
        if (input & 1)
            //cout<<index<<endl;
            result.push_back(1); 
        else
            result.push_back(0);
        input >>= 1;// dividing by two
        index++;
    }
    return result;
}

void change(int v, int k)
{
    int temp = pow(2,k);
    if(v<=temp)
    {
        vector<int> v1;
        v1 = changeBinary(v);
        for(int i=0;i<v1.size();i++)
        {
            if(v1[i]) cout<<"Coins of type "<<pow(2,i)<<"- "<<v1[i]<<endl;
        }
    }
    else
    {
        int cnt = 0;
        while(v>=temp)
        {
            v = v-temp;
            cnt++;
        }
        cout<<"Coins of type "<<temp<<"- "<<cnt<<endl;
        vector<int> v1;
        v1 = changeBinary(v);
        int t2 = v1.size();
        for(int i=t2-1;i>=0;i--)
        {
            if(v1[i]) cout<<"Coins of type "<<pow(2,i)<<"- "<<v1[i]<<endl;
        }
    }
}
Jinank Jain
  • 1
  • 1
    Welcome to MSE! Can you [edit] your answer to include a brief mathematical description of your algorithm, rather than just raw code? –  Jan 06 '16 at 07:30
  • 1
    Also, as you see, this question already has an accepted answer, which is quite a short algorithm. You seem to be doing essentially the same, but in many more steps. – Shailesh Jan 06 '16 at 07:45
0

I wrote this following algorithm in Ruby, quite similar to the C# one submitted by @Abstraction. However, there are a few minor changes here.

If you take a look are the parameters, k is being created without having to supply it in the beginning. Also, as soon as k reaches 0, the program will `return' and stop. 

def print_change(v, k = Math.log(v, 2).to_i, coin_value = 1)

  if k == 0
    puts "#{v} coins of denomination: #{coin_value}"
    return
  end

  if v % 2 == 1
    puts "1 coins of denomination: #{coin_value}"
  end

  print_change(v/2, k-1, coin_value*2)
end

I hope this helps!

HannibalBarca
  • 1