You have to pay a bill of exactly n rupees (no less or no more than n), where n is a positive integer (n > 0). You have unlimited access to the following coins (the coin amounts are in rupees): [3, 9, 36, 108, 540]. Your task is to determine if the payment of n rupees can be made using these available coins or not, if it is possible then you need to determine the minimum number of coins required to pay the bill.
Now, consider the following greedy strategy:
If n is not divisible by 3, return “Impossible”. Else:
Let payment_required = n, coins_used = 0
- Choose the largest coin smaller than or equal to payment_required, say a, and include it in the payment.
- Deduct the amount of selected coin from payment_required and increment coins_used, i.e. payment_required -= a, coins_used += 1
- If payment_required <= 0, return coins_used. Else repeat from step 1.
Which of the following option(s) are correct?
The greedy strategy mentioned above will give the correct answer for all possible choices of n.
The greedy strategy mentioned above will give the wrong answer for at least one possible choice of n.
There exists at least one n such that n is divisible by 3, but for this n the correct answer to the given question is “Impossible”, i.e. no choices of the given coins can sum to n.
For every possible n such that n is divisible by 3, it is always possible to pay exactly n rupees using the given coins in the question.