Sign Up

Have an account? Sign In Now

Sign In

Forgot Password?

Don't have account, Sign Up Here

Forgot Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Have an account? Sign In Now

Sorry, you do not have permission to ask a question, You must login to ask a question.

Forgot Password?

Need An Account, Sign Up Here
Sign InSign Up

SIKSHAPATH

SIKSHAPATH Logo SIKSHAPATH Logo

SIKSHAPATH Navigation

  • Home
  • Questions
  • Blog
    • Computer Science(CSE)
    • NPTEL
    • Startup
  • Shop
    • Internshala Answers
Search
Ask A Question

Mobile menu

Close
Ask a Question
  • Home
  • Questions
  • Blog
    • Computer Science(CSE)
    • NPTEL
    • Startup
  • Shop
    • Internshala Answers
Home/Questions/Q 20966
Next
kalakonda neha
  • 0
kalakonda neha
Asked: August 17, 20222022-08-17T21:45:37+05:30 2022-08-17T21:45:37+05:30In: Computer Science

You have to pay a bill of exactly n rupees …

  • 0

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

  1. Choose the largest coin smaller than or equal to payment_required, say a, and include it in the payment. 
  2. Deduct the amount of selected coin from payment_required and increment coins_used, i.e. payment_required -= a, coins_used += 1
  3. 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.

 

 

  • 0 0 Answers
  • 102 Views
  • 0 Followers
  • 0
Answer
Share
  • Facebook

    Leave an answer
    Cancel reply

    You must login to add an answer.

    Forgot Password?

    Need An Account, Sign Up Here

    Sidebar

    store ads

    Stats

    • Questions 1k
    • Answers 1k
    • Posts 127
    • Best Answers 66
    • LINEAR PROGRAMMING AND OPTIMIZATION TECHNIQUES NOTES
    • What is the Difference Between Section, Article and Aside in HTML5?
    • NPTEL Cloud Computing Assignment 3 Answers 2023
    • NPTEL Ethical Hacking Assignment 3 Answers 2023
    • NPTEL Problem Solving Through Programming In C Week 1 & 2 Assignment Answers 2023

    Explore

    • Recent Questions
    • Questions For You
    • Answers With Time
    • Most Visited
    • New Questions
    • Recent Questions With Time

    Footer

    Sikshapath Logo

    Helpful Links

    • Contact
    • Disclaimer
    • Privacy Policy Notice
    • TERMS OF USE
    • FAQs
    • Refund/Cancellation Policy
    • Delivery Policy for Sikshapath

    Follow Us

    © 2021-23 Sikshapath. All Rights Reserved

    Ads Blocker Image Powered by Code Help Pro

    Ads Blocker Detected!!!

    We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

    Refresh

    Insert/edit link

    Enter the destination URL

    Or link to existing content

      No search term specified. Showing recent items. Search or use up and down arrow keys to select an item.