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
  • 90 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 141
    • Best Answers 64
    • AI 101: Create Presentation Slide Using AI | Gamma App
    • What is the Difference Between Section, Article and Aside in HTML5?
    • How to enable or disable ChatGPT on the Windows 11 taskbar
    • NPTEL Data Mining Assignment Answers 2023 -Week 8
    • NPTEL Data Mining Assignment Answers 2023 -Week 7

    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
    Powered By
    Best Wordpress Adblock Detecting Plugin | CHP Adblock

    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.