Statistics

Problem Statement for "PouringWater"

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

  1. 3

    1

    Returns: 1

    The example from the problem statement.

  2. 13

    2

    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.

  3. 1000000

    5

    Returns: 15808

  4. 1

    1

    Returns: 0

  5. 1

    1000

    Returns: 0

  6. 10000000

    1

    Returns: 6777216

  7. 10000000

    2

    Returns: 485760

  8. 10000000

    1000

    Returns: 0

  9. 8388608

    1

    Returns: 0

  10. 8941948

    3

    Returns: 3716

  11. 8388607

    22

    Returns: 1

  12. 8388607

    23

    Returns: 0

  13. 8387584

    12

    Returns: 1024

  14. 8387584

    13

    Returns: 0

  15. 10000000

    1000

    Returns: 0

  16. 999999

    9

    Returns: 1

  17. 666

    2

    Returns: 102

  18. 8388609

    1

    Returns: 8388607

  19. 4414013

    1

    Returns: 3974595

  20. 7478469

    1

    Returns: 910139

  21. 5496348

    1

    Returns: 2892260

  22. 8325561

    1

    Returns: 63047

  23. 2836846

    1

    Returns: 1357458

  24. 62503

    1

    Returns: 3033

  25. 8800757

    1

    Returns: 7976459

  26. 8816669

    1

    Returns: 7960547

  27. 9439671

    1

    Returns: 7337545

  28. 9853251

    1

    Returns: 6923965

  29. 9883163

    2

    Returns: 602597

  30. 5222001

    2

    Returns: 20879

  31. 2646160

    2

    Returns: 499568

  32. 3538422

    2

    Returns: 655882

  33. 9582122

    2

    Returns: 903638

  34. 674320

    3

    Returns: 13808

  35. 9414628

    3

    Returns: 22556

  36. 240547

    3

    Returns: 21597

  37. 5417126

    3

    Returns: 87898

  38. 1327199

    3

    Returns: 16289

  39. 4592987

    4

    Returns: 2725

  40. 1300952

    4

    Returns: 9768

  41. 5045682

    4

    Returns: 590

  42. 4375782

    4

    Returns: 15130

  43. 7590137

    4

    Returns: 12039

  44. 5632545

    5

    Returns: 3551

  45. 9219160

    5

    Returns: 5032

  46. 2556304

    5

    Returns: 112

  47. 359025

    5

    Returns: 1423

  48. 2135180

    5

    Returns: 116

  49. 1

    10

    Returns: 0

  50. 1000000

    239

    Returns: 0

  51. 1

    100

    Returns: 0

  52. 10

    100

    Returns: 0

  53. 13

    50

    Returns: 0

  54. 1

    137

    Returns: 0

  55. 100000

    239

    Returns: 0

  56. 2

    10

    Returns: 0

  57. 511

    512

    Returns: 0

  58. 5

    20

    Returns: 0

  59. 10000000

    856

    Returns: 0

  60. 6767

    34

    Returns: 0

  61. 1

    2

    Returns: 0

  62. 9

    3

    Returns: 0

  63. 1

    4

    Returns: 0

  64. 173141

    31

    Returns: 0

  65. 8388615

    2

    Returns: 1

  66. 2

    4

    Returns: 0

  67. 2

    5

    Returns: 0

  68. 4

    70

    Returns: 0

  69. 9990000

    7

    Returns: 144

  70. 3

    5

    Returns: 0

  71. 5

    1

    Returns: 3

  72. 5

    10

    Returns: 0

  73. 1

    5

    Returns: 0

  74. 5

    100

    Returns: 0

  75. 993445

    43

    Returns: 0

  76. 4

    444

    Returns: 0

  77. 500

    1000

    Returns: 0

  78. 3452343

    234

    Returns: 0

  79. 85

    4

    Returns: 0

  80. 2

    100

    Returns: 0

  81. 4

    8

    Returns: 0

  82. 5

    2

    Returns: 0

  83. 14

    2

    Returns: 2

  84. 16

    17

    Returns: 0

  85. 3602

    3

    Returns: 494

  86. 21

    3

    Returns: 0

  87. 1

    3

    Returns: 0

  88. 4

    100

    Returns: 0

  89. 3

    99

    Returns: 0

  90. 3

    6

    Returns: 0

  91. 13

    1000

    Returns: 0

  92. 10000000

    100

    Returns: 0

  93. 283686

    8

    Returns: 0

  94. 43

    3

    Returns: 1

  95. 8

    10

    Returns: 0

  96. 20356

    2

    Returns: 124

  97. 19

    2

    Returns: 1

  98. 458746

    999

    Returns: 0

  99. 2

    23

    Returns: 0

  100. 128

    3

    Returns: 0

  101. 5

    3

    Returns: 0

  102. 9000000

    1

    Returns: 7777216

  103. 898989

    4

    Returns: 18515

  104. 5

    500

    Returns: 0

  105. 11

    10

    Returns: 0

  106. 10000000

    3

    Returns: 485760

  107. 8388607

    1000

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: