Tessellate S.T.E.M.S - Computer Science - School - Set 1 - Problem 5

Computer Science Level 2

We have coins of values 1, 3, 7 and 13. And, we need to pay N. We wanted to figure out the minimum number of coins required to pay the amount N.

Consider the following algorithm: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
SET ans := 0
SET n := N

WHILE (n  > 0):
    IF (n > 13):
        INCREMENT ans
        SET n := n - 13
    ELSE IF (n > 7):
        INCREMENT ans
        SET n := n - 7
    ELSE IF (n > 3):
        INCREMENT ans
        SET n := n - 3
    ELSE IF (n >1)
        INCREMENT ans
        SET n := n - 1 

OUTPUT ans

What can you say about this algorithm?

This problem is a part of Tessellate S.T.E.M.S.

The algorithm does not always gives us the minimum number of coins we need to pay N The algorithm never gives us the minimum number of coins we need to pay N The algorithm computes ⌊ m a x i m u m 2 ⌋ \lfloor \frac{maximum}{2} \rfloor number of coins we need to pay N The algorithm computes minimum number of coins we need to pay N

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

0 solutions

No explanations have been posted yet. Check back later!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...