Problem Statement |
| | You have N bottles, each with unlimited capacity. Initially, each bottle contains exactly 1 liter of water. You want to carry these bottles to another location, but you can only carry K bottles at a time. You don't want to waste any water and you don't want to make more than one trip, so you decide to redistribute the contents of the bottles until you end up with no more than K non-empty bottles.
You are only allowed to redistribute your water using the following method. First, pick two bottles that contain an equal amount of water. Then, pour the entire content of one of those bottles into the other. Repeat this process as many times as necessary.
Because of this restriction, it may be impossible to end up with no more than K non-empty bottles using only the N bottles that you have initially. Fortunately, you can also buy more bottles. Each bottle that you buy will contain exactly 1 liter of water and have unlimited capacity. For example, consider the case where N is 3 and K is 1. It's impossible to get from 3 bottles to 1. If you pour one bottle into another, you end up with one 2 liter bottle and one 1 liter bottle. At that point, you're stuck. However, if you then buy another bottle, you can pour that bottle into the 1 liter bottle, and pour the resulting 2 liter bottle into the other 2 liter bottle to end up with just one 4 liter bottle.
Return the minimum number of additional bottles you must buy in order to achieve your goal. If it's impossible, return -1 instead. |
| |
Definition |
| | | Class: | PouringWater | | Method: | getMinBottles | | Parameters: | int, int | | Returns: | int | | Method signature: | int getMinBottles(int N, int K) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | N will be between 1 and 10^7, inclusive. |
| - | K will be between 1 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 1 | | The example from the problem statement. |
|
|
| 1) | |
| | | Returns: 3 | | If you have 13, 14, or 15 bottles, you can't end up with one or two bottles. With 16 bottles, you can end up with one bottle. |
|
|
| 2) | |
| | |