Statistics

Problem Statement for "Chocolate"

Problem Statement

You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2 x 2 chocolate bar can be divided into two 2 x 1 pieces, but it cannot be divided into two pieces, where one of them is 1 x 1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces. Your goal is to create a piece consisting of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.

Definition

Class:
Chocolate
Method:
minSplitNumber
Parameters:
int, int, int
Returns:
int
Method signature:
int minSplitNumber(int width, int height, int nTiles)
(be sure your method is public)

Constraints

  • width will be between 1 and 10^9, inclusive.
  • height will be between 1 and 10^9, inclusive.
  • nTiles will be between 1 and 10^9, inclusive.

Examples

  1. 5

    4

    12

    Returns: 1

    You can split the chocolate bar into two rectangular pieces 3 x 4 and 2 x 4 by creating a single vertical break. Only one break is necessary.

  2. 12

    10

    120

    Returns: 0

    The chocolate bar consists of exactly 120 tiles.

  3. 2

    2

    1

    Returns: 2

  4. 17

    19

    111

    Returns: -1

  5. 10

    5

    86

    Returns: -1

  6. 3

    1000

    591991886

    Returns: -1

  7. 4

    99856

    608109

    Returns: -1

  8. 10

    9998244

    90148109

    Returns: -1

  9. 10

    1000000000

    463372

    Returns: 2

  10. 600

    2

    874960160

    Returns: -1

  11. 1000

    1000

    658705

    Returns: -1

  12. 961

    100000

    992400000

    Returns: -1

  13. 1000

    10000000

    195128606

    Returns: -1

  14. 324

    1000000000

    816377382

    Returns: 2

  15. 100000

    10

    102836

    Returns: 2

  16. 100000

    378

    20556018

    Returns: 1

  17. 99856

    100000

    272273400

    Returns: 2

  18. 100000

    9998244

    426746880

    Returns: 2

  19. 61740

    999950884

    941584258

    Returns: 2

  20. 3704400

    9

    425297658

    Returns: -1

  21. 10000000

    961

    476280000

    Returns: 2

  22. 3110400

    100000

    997963316

    Returns: -1

  23. 10000000

    10000000

    916034129

    Returns: -1

  24. 9998244

    999950884

    940567039

    Returns: 2

  25. 1000000000

    9

    979912316

    Returns: 2

  26. 1000000000

    961

    978646059

    Returns: 2

  27. 1000000000

    99856

    956536183

    Returns: 2

  28. 226800000

    10000000

    938071715

    Returns: 2

  29. 999950884

    1000000000

    998303693

    Returns: 2

  30. 282475249

    282475249

    311169600

    Returns: 2

  31. 282475249

    282475249

    282475249

    Returns: 1

  32. 282475249

    282475249

    276131207

    Returns: 2

  33. 282475249

    282475249

    282475249

    Returns: 1

  34. 48384000

    282475249

    947683037

    Returns: 2

  35. 282475249

    282475249

    564950498

    Returns: 1

  36. 282475249

    282475249

    847425747

    Returns: 1

  37. 282475249

    282475249

    564950498

    Returns: 1

  38. 282475249

    282475249

    282475249

    Returns: 1

  39. 282475249

    282475249

    944389725

    Returns: 2

  40. 282475249

    282475249

    564950498

    Returns: 1

  41. 74680704

    112021056

    149361408

    Returns: 1

  42. 149361408

    282475249

    564950498

    Returns: 1

  43. 282475249

    282475249

    847425747

    Returns: 1

  44. 282475249

    282475249

    656641603

    Returns: -1

  45. 282475249

    282475249

    492705233

    Returns: 2

  46. 99532800

    282475249

    99532800

    Returns: 1

  47. 282475249

    282475249

    24938842

    Returns: 2

  48. 282475249

    282475249

    160030080

    Returns: 2

  49. 61740000

    41489280

    635040000

    Returns: 2

  50. 282475249

    60963840

    695667047

    Returns: 2

  51. 282475249

    282475249

    282475249

    Returns: 1

  52. 282475249

    282475249

    917628732

    Returns: 2

  53. 282475249

    65318400

    847425747

    Returns: 1

  54. 282475249

    164640000

    987840000

    Returns: 1

  55. 4

    3

    20

    Returns: -1

  56. 1

    3

    53

    Returns: -1

  57. 14

    6

    54

    Returns: 1

  58. 10

    18

    393

    Returns: -1

  59. 6

    22

    280

    Returns: -1

  60. 12

    21

    302

    Returns: -1

  61. 4

    11

    758

    Returns: -1

  62. 32

    13

    1433

    Returns: -1

  63. 14

    41

    1805

    Returns: -1

  64. 6

    41

    1888

    Returns: -1

  65. 1000000000

    1000000000

    1000000000

    Returns: 1

  66. 1

    1000000000

    1000000000

    Returns: 0

  67. 10

    100000000

    1000000000

    Returns: 0

  68. 100

    10000000

    1000000000

    Returns: 0

  69. 1000000

    1000

    1000000000

    Returns: 0

  70. 10000000

    100

    1000000000

    Returns: 0

  71. 100000000

    10

    1000000000

    Returns: 0

  72. 1000000000

    1

    1000000000

    Returns: 0

  73. 100000000

    100000000

    1000000000

    Returns: 1

  74. 40000

    40000

    900060001

    Returns: 2

  75. 10089

    26481

    246414661

    Returns: 2

  76. 4652

    2678

    10724209

    Returns: 2

  77. 4970

    28477

    112380529

    Returns: 2

  78. 4203

    21548

    83664487

    Returns: 2

  79. 12800

    26804

    318981023

    Returns: 2

  80. 20915

    7509

    150865069

    Returns: 2

  81. 27302

    4356

    105393667

    Returns: 2

  82. 30752

    12908

    363073121

    Returns: 2

  83. 20176

    27507

    535291069

    Returns: 2

  84. 14795

    3856

    47004557

    Returns: 2

  85. 193

    193

    37249

    Returns: 0

  86. 2092

    2093

    4355569

    Returns: 2

  87. 2923

    2910

    8462281

    Returns: 2

  88. 30341

    30344

    920576281

    Returns: 1

  89. 11450

    11454

    130484929

    Returns: 2

  90. 1234567

    7654321

    844062807

    Returns: 2

  91. 100000000

    3

    199999996

    Returns: 2

  92. 3

    100000000

    199999996

    Returns: 2

  93. 65537

    65537

    131073

    Returns: 2

  94. 200

    1000000000

    600

    Returns: 1

  95. 1000000000

    5

    705032704

    Returns: 2

  96. 2

    20

    25

    Returns: -1

  97. 4

    2

    3

    Returns: 2

  98. 5

    5

    100

    Returns: -1

  99. 1000000000

    1000000000

    50

    Returns: 2

  100. 1

    10

    100

    Returns: -1

  101. 2

    3

    8

    Returns: -1

  102. 1000000000

    1000000000

    1000000000

    Returns: 1

  103. 945454926

    945454926

    945454927

    Returns: -1

  104. 999999999

    999999999

    900095849

    Returns: 2

  105. 6

    1

    12

    Returns: -1

  106. 2

    2

    160

    Returns: -1

  107. 333333

    555555

    501221087

    Returns: -1

  108. 5

    12

    10

    Returns: 1

  109. 1000000000

    1000000000

    3

    Returns: 2

  110. 1000000000

    1000000000

    5

    Returns: 2

  111. 2

    10

    100

    Returns: -1

  112. 1000000

    35000

    640261632

    Returns: 2

  113. 1000000

    1000000

    1000000000

    Returns: 1

  114. 189

    3

    203

    Returns: -1

  115. 2

    999999998

    999999999

    Returns: -1

  116. 1000000000

    1000000000

    11111117

    Returns: 2

  117. 10

    10

    1000

    Returns: -1

  118. 999999999

    999999999

    1000000000

    Returns: 2

  119. 10

    20

    143

    Returns: -1

  120. 1000034

    1009283

    1062

    Returns: 2

  121. 5

    5

    30

    Returns: -1

  122. 5

    1

    10

    Returns: -1

  123. 5

    4

    6

    Returns: 2

  124. 2

    5

    15

    Returns: -1

  125. 1000000000

    1000000000

    1

    Returns: 2

  126. 999999901

    999999901

    999999937

    Returns: -1

  127. 919387247

    929666241

    971259251

    Returns: -1

  128. 2

    1

    2

    Returns: 0

  129. 2

    100000

    10000

    Returns: 1

  130. 1000000

    100000000

    276447232

    Returns: 2

  131. 65536

    65536

    43

    Returns: 2

  132. 2

    20

    39

    Returns: -1

  133. 10

    10

    5

    Returns: 2

  134. 3

    5

    25

    Returns: -1

  135. 2

    7

    7

    Returns: 1

  136. 65536

    65537

    65536

    Returns: 1

  137. 65536

    65536

    12

    Returns: 2

  138. 10

    10

    81

    Returns: 2

  139. 536870908

    536870908

    999999999

    Returns: 2

  140. 1000000000

    39171367

    78342734

    Returns: 1

  141. 1000000000

    1000000000

    100000000

    Returns: 2

  142. 899999999

    899999999

    930000017

    Returns: -1

  143. 4

    10

    35

    Returns: -1

  144. 7

    7

    36

    Returns: 2

  145. 10

    1

    20

    Returns: -1

  146. 999994986

    999994986

    999994987

    Returns: -1

  147. 10000

    3500000

    640261632

    Returns: 2

  148. 4

    4

    6

    Returns: 2

  149. 100000000

    100000000

    268435456

    Returns: 2

  150. 9999999

    9999997

    1000000000

    Returns: 2

  151. 13

    1

    13

    Returns: 0

  152. 3

    3

    27

    Returns: -1

  153. 999999999

    3

    1000000000

    Returns: 2

  154. 1000000

    5000

    705032704

    Returns: 2

  155. 500000000

    500000000

    888765401

    Returns: -1

  156. 1000000000

    1000000000

    999999999

    Returns: 2

  157. 999999935

    999999936

    999999937

    Returns: -1

  158. 3

    9

    6

    Returns: 1

  159. 6

    9

    6

    Returns: 1

  160. 65537

    65536

    65536

    Returns: 1

  161. 31622

    31622

    999979237

    Returns: -1

  162. 31622

    31622

    1000000000

    Returns: -1

  163. 1000000000

    1000000000

    232434354

    Returns: 2

  164. 10000000

    10000000

    12345

    Returns: 2

  165. 524288

    8228

    18874368

    Returns: 1

  166. 1000000000

    5

    1000000000

    Returns: 1

  167. 999999999

    3

    10

    Returns: 2

  168. 2

    4

    10

    Returns: -1

  169. 12

    10

    120

    Returns: 0

  170. 1000000

    1000000

    10000000

    Returns: 1

  171. 2

    2

    8

    Returns: -1

  172. 999999999

    999999999

    808348673

    Returns: 2

  173. 10000000

    1000000

    4000

    Returns: 2

  174. 1000000000

    50000000

    784662528

    Returns: 2

  175. 3

    3

    8

    Returns: -1

  176. 3

    17

    17

    Returns: 1

  177. 3

    15

    26

    Returns: 2

  178. 1

    1

    999999997

    Returns: -1

  179. 1000000000

    1000000000

    12345452

    Returns: 2

  180. 22000

    999999999

    999999999

    Returns: 1

  181. 1000000000

    1000000000

    2

    Returns: 2

  182. 4

    2

    16

    Returns: -1

  183. 65536

    65552

    1048576

    Returns: 1

  184. 6

    19

    95

    Returns: 1

  185. 1

    5

    5

    Returns: 0

  186. 1048576

    1048577

    1048576

    Returns: 1

  187. 200000

    900000

    100

    Returns: 2

  188. 2

    8

    3

    Returns: 2

  189. 4

    5

    5

    Returns: 1

  190. 3

    3

    1

    Returns: 2

  191. 149000

    149000

    726163520

    Returns: 2

  192. 1000000000

    1000000000

    999999929

    Returns: 2

  193. 31266

    250000

    1000000000

    Returns: 1

  194. 131072

    131073

    131072

    Returns: 1

  195. 6

    5

    35

    Returns: -1

  196. 1

    2

    1

    Returns: 1

  197. 999999936

    999999936

    999999937

    Returns: -1

  198. 1000000000

    1000000000

    200

    Returns: 2

  199. 999999999

    777777777

    10000001

    Returns: 2

  200. 1000000000

    1000000000

    4556

    Returns: 2

  201. 1048577

    1048577

    2097153

    Returns: 2

  202. 93479234

    93749237

    3242342

    Returns: 2

  203. 65536

    65536

    100000

    Returns: 2

  204. 2

    500000000

    999999999

    Returns: -1

  205. 1

    1

    2

    Returns: -1

  206. 10

    50

    20

    Returns: 1

  207. 4

    4

    9

    Returns: 2

  208. 1

    1

    500

    Returns: -1

  209. 542288

    8228

    18874368

    Returns: 2

  210. 2

    2

    4

    Returns: 0

  211. 99

    99

    999999999

    Returns: -1

  212. 2

    2

    2

    Returns: 1

  213. 500000000

    500000000

    1000000000

    Returns: 1

  214. 10

    20

    12

    Returns: 2

  215. 999999999

    1

    1

    Returns: 1

  216. 65536

    65536

    6

    Returns: 2

  217. 900000000

    900000000

    900001171

    Returns: -1

  218. 2

    20

    21

    Returns: -1

  219. 1000000

    1000000

    100000000

    Returns: 1

  220. 10000000

    10000000

    276447232

    Returns: 2

  221. 7

    41

    70

    Returns: 1

  222. 29

    9

    238

    Returns: -1

  223. 1

    1

    10

    Returns: -1

  224. 2

    2

    10

    Returns: -1

  225. 8

    11

    90

    Returns: -1

  226. 10

    10

    200

    Returns: -1

  227. 100000000

    100

    3245200

    Returns: 1

  228. 536862800

    536862800

    5

    Returns: 2

  229. 51000

    100000

    805032704

    Returns: 2

  230. 99999998

    99999999

    999999999

    Returns: 2

  231. 4

    10

    10

    Returns: 1

  232. 200000014

    2

    100000007

    Returns: 2

  233. 999999999

    2

    999999999

    Returns: 1

  234. 8

    8

    49

    Returns: 2

  235. 3

    3

    4

    Returns: 2

  236. 1000000000

    1000000000

    111

    Returns: 2

  237. 12345678

    999999999

    999999998

    Returns: 2

  238. 999999999

    999999999

    999999998

    Returns: 2

  239. 7

    7

    12

    Returns: 2

  240. 6

    8

    35

    Returns: 2

  241. 3

    10

    20

    Returns: 1

  242. 1000000000

    1000000000

    999999997

    Returns: 2

  243. 6

    3

    24

    Returns: -1

  244. 1000000000

    1000000000

    99999999

    Returns: 2

  245. 5000000

    1000000

    658067456

    Returns: 2

  246. 1000000000

    1000000000

    10

    Returns: 2

  247. 999999998

    999999998

    999999999

    Returns: 2

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: