Question

You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?

(a) 15

(b) 16

(c) 17

(d) 4

This question was posed to me in examination.

My enquiry is from Coin Change Problem topic in chapter Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right answer is (d) 4

The explanation is: Sums can be achieved as follows:

15 = {5,5,5}

16 = {3,3,5,5}

17 = {3,7,7}

we can’t achieve for sum=4 because our available denominations are 3,5,7 and sum of any two denominations is greater than 4.