Problem Statement
You have a number of coins that you have been saving for a special occasion. That occasion has come, and you want to know how many coins you have. In order to do this you must count them.
However, you have quite a few coins, and you want to find a way to optimize your counting abilities. Therefore, you come up with a way to count them faster than one at a time. Here is how it works:
While there are still coins left:
1) You create a stack of 5 coins by placing one coin at a time on the stack. This takes 5 seconds, 1 for each coin.
2) You take another bunch of coins in your hand, manipulating them until they all stack on top of one another, which takes 1 second. You then put the stack next to the 5 coin stack formed in step 1, and slide off the coins that are higher (if any) than that stack, creating another stack of 5. This takes 1 more second (each time you perform this step, you have counted 5 more coins in 2 seconds). You perform this step up to four times to get a total of 25 coins (5 from step 1, and 20 from four step 2's).
3) You then take all of these coins and throw them into a bag, which takes 1 second.
4) Go back to step 1.
Steps 1 and 2 count 5 coins each. If you get to step 1 or 2 and have less than 5 coins left, you count the coins individually (taking 1 second per coin), and you finish by throwing the last batch of coins in the bag, which takes 1 more second. If you get to step 2 with 0 coins left, you should throw the batch you have built so far into the bag, which takes 1 second. If you get back to step 1 and have no coins left, you have not started a new batch. Therefore, you do not need to add any more seconds to the time, you are done.
Create a class CoinStacks that contains the method count, which has one argument:
coins: the number of coins to count
The method should return an int, which should be how many seconds it takes to count the coins by using the above stated method.
Definition
- Class:
- CoinStacks
- Method:
- count
- Parameters:
- int
- Returns:
- int
- Method signature:
- int count(int coins)
- (be sure your method is public)
Notes
- You can tell when you have less than 5 coins left, so if the last stack of coins is less than 5 coins, you do not need to compare it to another stack, but you must still count them individually (see example 1). This takes 1 second per coin.
- The last batch is always thrown in the bag, even if it is not a full 25 coins. This will take 1 second.
- All coins have exactly the same dimensions.
- You always grab at least 5 coins when stacking them up against another pile of 5.
- If you start out with less than 5 coins, count them individually, and throw them in the bag. This takes 1 second per coin and 1 second to throw in the bag.
Constraints
- coins is between 0 and 10000 inclusive.
Examples
8
Returns: 9
You start by stacking up the first 5, then, since you notice there are less than 5 left, you don't even bother comparing them to the first stack of 5, you just count them individually. Finally, you throw the coins into the bag. Total time is 5 + 3 + 1 = 9 seconds.
10
Returns: 8
You stack up the first 5 coins, taking 5 seconds. Then, in step 2 you match another stack of 5 coins, taking 2 more seconds. Since you don't have any more coins left for another step 2, you throw all the coins you have in the bag, and you are done. 5 + 2 + 1 = 8 seconds.
9
Returns: 10
Same as the previous example 1, except that now, you count 4 more coins instead of 3 more. 5 + 4 + 1 = 10.
1234
Returns: 696
5678
Returns: 3182
9999
Returns: 5602
11
Returns: 9
Perform step 1, perform step 2, you now have 1 coin left. Count it individually (this takes 1 second), and throw in the bag. 5 + 2 + 1 + 1 = 9.
1
Returns: 2
2
Returns: 3
3
Returns: 4
4
Returns: 5
5
Returns: 6
6
Returns: 7
7
Returns: 8
200
Returns: 112
10000
Returns: 5600
12
Returns: 10
13
Returns: 11
14
Returns: 12
15
Returns: 10
16
Returns: 11
17
Returns: 12
18
Returns: 13
19
Returns: 14
20
Returns: 12
21
Returns: 13
22
Returns: 14
23
Returns: 15
24
Returns: 16
25
Returns: 14
0
Returns: 0
10000
Returns: 5600
200
Returns: 112
4
Returns: 5
24
Returns: 16
3
Returns: 4
29
Returns: 19
10
Returns: 8
2
Returns: 3
5
Returns: 6
25
Returns: 14
13
Returns: 11
1
Returns: 2
0
Returns: 0
10000
Returns: 5600
200
Returns: 112
4
Returns: 5
24
Returns: 16
3
Returns: 4
29
Returns: 19
10
Returns: 8
2
Returns: 3
5
Returns: 6
25
Returns: 14
13
Returns: 11
1
Returns: 2