Question

5. (3 points) Consider a hypothetical country Binary Land where they only use coins. There are n types of coins of denominations 1, 21, 22, 2,..., 2-1. Suppose you are a bank teller in Binary Land and your job is to give money to customers for any requested value V that is an integer. You should minimize the number of coins while paying V units of money. Design an algorithm that takes V as input and outputs the payment method that minimizes the total number of coins. Give pseudocode. Prove that your algorithm returns an optimal solution and discuss running time of your algorithm. (The output can be an array containing non-negative integers (81, 82, ..., Sn such that: Si=1 si 2-1 =V.)

Answer 1

== Helper Algorithm ==

Is_ith_Bit_Set(Num, i) :

if ( ( (2 ^ i) bitwise-AND (Num) ) > 0 ) : then return true

else : return false

  

== Main Algorithm ==

Get_Number_Of_Coins (V) :

1 :

Let n <- Number of coins available, so that coins of denominations (2 ^ 0), (2 ^ 1) ... (2 ^ (n-1)) are available.

2 :

Let N(V) <- floor(V / (2 ^ (n - 1)))

i.e. N(V) is the quotient (rounded to nearest lower integer if required) when V is divided by (2 ^ (n - 1))

3 :

Let R(V) <- V mod (2 ^ (n - 1))

i.e. R(V) is the remainder when V is divided by (2 ^ (n - 1))

4 :

Now, for the particular i'th bit set in the binary-representation for (2 ^ (n - 1)), coin of that particular denomination, multiplied by N(V), needs to be taken.

5:

Additionally, for every i'th bit set in the binary representation of R(V), 1 coin each for that particular denomination, needs to be taken.

Examples :

Let n = 5, so that coins of denominations (2 ^ 0), (2 ^ 1), (2 ^ 2), (2 ^ 3), (2 ^ 4) are available.

That is, coins of denominations, 1, 2, 4, 8, 16 are available.

• V = 14
  • N(V) = floor(V / (2 ^ (n - 1))) = floor(14 / (2 ^ 4)) = floor(14 / 16) = 0
  • R(V) = V mod (2 ^ (n - 1)) = 14 mod (2 ^ (4)) = 14 mod 16 = 14
  • Now, binary representation for (2 ^ (n - 1)), i.e. 16 is 0001 0000 (indexing is from right, beginning with 0). So, N(V) coins of (2 ^ 4) are required. That is, 0 coins of 16.
  • Now, binary representation of R(V), i.e. 14 is 0000 1110 (indexing from right, beginning with 0). So, 1 coins each of (2 ^ 1), (2 ^ 2), (2 ^ 3) are required. That is, 1 coins each of 2, 4, 8.
  • In total, we require
    • 0 coins of 1
    • 1 coins of 2
    • 1 coins of 4
    • 1 coins of 8
    • 0 coins of 16
• V = 29
  • N(V) = floor(V / (2 ^ (n - 1))) = floor(29 / (2 ^ 4)) = floor(29 / 16) = 1
  • R(V) = V mod (2 ^ (n - 1)) = 29 mod (2 ^ (4)) = 29 mod 16 = 13
  • Now, binary representation for (2 ^ (n - 1)), i.e. 16 is 0001 0000 (indexing is from right, beginning with 0). So, N(V) coins of (2 ^ 4) are required. That is, 1 coins of 16.
  • Now, binary representation of R(V), i.e. 13 is 0000 1101 (indexing from right, beginning with 0). So, 1 coins each of (2 ^ 0), (2 ^ 2), (2 ^ 3) are required. That is, 1 coins each of 1, 4, 8.
  • In total, we require
    • 1 coins of 1
    • 0 coins of 2
    • 1 coins of 4
    • 1 coins of 8
    • 1 coins of 16
• V = 200
  • N(V) = floor(V / (2 ^ (n - 1))) = floor(200 / (2 ^ 4)) = floor(200 / 16) = 12
  • R(V) = V mod (2 ^ (n - 1)) = 200 mod (2 ^ (4)) = 200 mod 16 = 8
  • Now, binary representation for (2 ^ (n - 1)), i.e. 16 is 0001 0000 (indexing is from right, beginning with 0). So, N(V) coins of (2 ^ 4) are required. That is, 12 coins of 16.
  • Now, binary representation of R(V), i.e. 8 is 0000 1000 (indexing from right, beginning with 0). So, 1 coins each of (2 ^ 3) are required. That is, 1 coins each of 8.
  • In total, we require
    • 0 coins of 1
    • 0 coins of 2
    • 0 coins of 4
    • 1 coins of 8
    • 12 coins of 16

Running-Time :

Since we are dealing only in binary, so the running time is O(lg V). In other words, O(number of bits for the integer word on a computer).