Statistics

Problem Statement for "MyVeryLongCake"

Problem Statement

You have a long thin cake. For simplicity, we can consider the cake to be one-dimensional. The length of the cake is n.

You are expecting some friends. You are going to cut the cake into multiple pieces before the friends arrive.

When the friends arrive, you will divide the cake among them, using the following procedure: starting at the beginning of the cake, you will first give some consecutive pieces to your first friend, then some consecutive pieces to your second friend, and so on.

Of course, you want to be fair. That is, each of your friends should receive the same total amount of cake. (The number of pieces may be different for different friends, but the sum of their lengths must be the same.)

As we stated above, you want to cut the cake before your friends arrive. However, you don't know how many friends will actually come. You only know that their count will be a divisor of n smaller than n.

You are given the int n. You want to cut the cake in such a way that for each valid number of friends it will be possible to give each of them the same amount of cake when using the above procedure. Return the smallest possible number of pieces after you cut the cake.

Definition

Class:
MyVeryLongCake
Method:
cut
Parameters:
int
Returns:
int
Method signature:
int cut(int n)
(be sure your method is public)

Constraints

  • n will be between 2 and 1,000,000,000, inclusive.

Examples

  1. 6

    Returns: 4

    The best possible solution is to cut the cake into 4 pieces. Let's call the pieces A, B, C, and D, in order. Their lengths will be 2, 1, 1, and 2. As n=6, there will be 1, 2, or 3 friends. If there is just one friend, she gets all four pieces. If there are two friends, the first gets A+B and the second gets C+D. If there are three friends, the first gets A, the second gets B+C, and the third gets D. Note that the order of parts matters. For example, dividing the cake into parts of length 2, 1, 2, and 1 is not a valid solution.

  2. 3

    Returns: 1

    In this case, the only possible number of friends that will come to your house is 1. Hence, you don't even need to cut the cake, simply leave it in one piece.

  3. 15

    Returns: 7

    You are expecting 1, 3, or 5 friends.

  4. 1000000000

    Returns: 600000000

  5. 223092870

    Returns: 186597510

  6. 473828165

    Returns: 117377861

  7. 209144467

    Returns: 29877787

  8. 290540586

    Returns: 207529002

  9. 829032593

    Returns: 4631645

  10. 577007436

    Returns: 384671628

  11. 924295281

    Returns: 436755921

  12. 427401489

    Returns: 142526433

  13. 577173928

    Returns: 288586968

  14. 386071616

    Returns: 225091136

  15. 97538621

    Returns: 1

  16. 887608573

    Returns: 52212285

  17. 901849846

    Returns: 454104310

  18. 899842149

    Returns: 299947401

  19. 840821047

    Returns: 78115447

  20. 674100155

    Returns: 134820035

  21. 2

    Returns: 1

  22. 1000000000

    Returns: 600000000

  23. 3

    Returns: 1

  24. 999999999

    Returns: 351353295

  25. 4

    Returns: 2

  26. 999999998

    Returns: 500724278

  27. 5

    Returns: 1

  28. 999999997

    Returns: 14679997

  29. 6

    Returns: 4

  30. 999999996

    Returns: 666666668

  31. 7

    Returns: 1

  32. 999999995

    Returns: 210044411

  33. 8

    Returns: 4

  34. 999999994

    Returns: 571428574

  35. 9

    Returns: 3

  36. 999999993

    Returns: 372549049

  37. 10

    Returns: 6

  38. 999999992

    Returns: 501003992

  39. 11

    Returns: 1

  40. 999999991

    Returns: 14925439

  41. 2

    Returns: 1

  42. 536870912

    Returns: 268435456

  43. 3

    Returns: 1

  44. 387420489

    Returns: 129140163

  45. 5

    Returns: 1

  46. 244140625

    Returns: 48828125

  47. 7

    Returns: 1

  48. 282475249

    Returns: 40353607

  49. 11

    Returns: 1

  50. 214358881

    Returns: 19487171

  51. 23

    Returns: 1

  52. 148035889

    Returns: 6436343

  53. 53

    Returns: 1

  54. 418195493

    Returns: 7890481

  55. 113

    Returns: 1

  56. 163047361

    Returns: 1442897

  57. 271

    Returns: 1

  58. 19902511

    Returns: 73441

  59. 997

    Returns: 1

  60. 991026973

    Returns: 994009

  61. 4001

    Returns: 1

  62. 16008001

    Returns: 4001

  63. 9973

    Returns: 1

  64. 99460729

    Returns: 9973

  65. 10301

    Returns: 1

  66. 106110601

    Returns: 10301

  67. 31607

    Returns: 1

  68. 999002449

    Returns: 31607

  69. 100003

    Returns: 1

  70. 199999

    Returns: 1

  71. 599999

    Returns: 1

  72. 2999999

    Returns: 1

  73. 29999999

    Returns: 1

  74. 89999999

    Returns: 1

  75. 599999971

    Returns: 1

  76. 999999937

    Returns: 1

  77. 999983

    Returns: 1

  78. 2

    Returns: 1

  79. 6

    Returns: 4

  80. 30

    Returns: 22

  81. 210

    Returns: 162

  82. 2310

    Returns: 1830

  83. 30030

    Returns: 24270

  84. 510510

    Returns: 418350

  85. 9699690

    Returns: 8040810

  86. 460642897

    Returns: 116010577

  87. 99799811

    Returns: 19979

  88. 999983

    Returns: 1

  89. 31607

    Returns: 1

  90. 33331

    Returns: 1

  91. 999999937

    Returns: 1

  92. 700209804

    Returns: 511936908

  93. 189167895

    Returns: 107245143

  94. 999983

    Returns: 1

  95. 633922289

    Returns: 201965489

  96. 4333030

    Returns: 2733190

  97. 6534290

    Returns: 4536722

  98. 61370

    Returns: 39482

  99. 655246046

    Returns: 409695518

  100. 178487505

    Returns: 101695185

  101. 31607

    Returns: 1

  102. 546750000

    Returns: 400950000

  103. 364500000

    Returns: 267300000

  104. 656100000

    Returns: 481140000

  105. 787320000

    Returns: 577368000

  106. 874800000

    Returns: 641520000

  107. 450000000

    Returns: 330000000

  108. 984150000

    Returns: 721710000

  109. 911250000

    Returns: 668250000

  110. 729000000

    Returns: 534600000

  111. 492075000

    Returns: 360855000

  112. 777924000

    Returns: 600112800

  113. 540225000

    Returns: 416745000

  114. 907578000

    Returns: 700131600

  115. 432180000

    Returns: 333396000

  116. 555660000

    Returns: 428652000

  117. 226894500

    Returns: 175032900

  118. 463050000

    Returns: 357210000

  119. 622339200

    Returns: 480090240

  120. 533433600

    Returns: 411505920

  121. 147061250

    Returns: 96640250

  122. 762300000

    Returns: 603900000

  123. 216090000

    Returns: 166698000

  124. 914760000

    Returns: 724680000

  125. 205439850

    Returns: 162751050

  126. 332057880

    Returns: 263058840

  127. 102910500

    Returns: 81526500

  128. 719039475

    Returns: 420217875

  129. 494133750

    Returns: 374343750

  130. 903935340

    Returns: 716104620

  131. 636693750

    Returns: 504393750

  132. 755795040

    Returns: 610827360

  133. 979642300

    Returns: 669601660

  134. 163963800

    Returns: 132514200

  135. 157907178

    Returns: 113737338

  136. 274542345

    Returns: 160446825

  137. 307041735

    Returns: 189255495

  138. 123873750

    Returns: 100113750

  139. 277477200

    Returns: 224254800

  140. 738499580

    Returns: 504776636

  141. 96192096

    Returns: 73129056

  142. 304504200

    Returns: 246097800

  143. 311424750

    Returns: 245717550

  144. 193297650

    Returns: 154913010

  145. 917751120

    Returns: 724460880

  146. 567451500

    Returns: 456475500

  147. 208288080

    Returns: 170686800

  148. 728377650

    Returns: 588668850

  149. 290603950

    Returns: 204042670

  150. 490964760

    Returns: 387561240

  151. 545044500

    Returns: 440500500

  152. 604819761

    Returns: 320363313

  153. 760014801

    Returns: 402567633

  154. 83811156

    Returns: 61746516

  155. 962914680

    Returns: 781764984

  156. 627477565

    Returns: 251879485

  157. 441833315

    Returns: 196249955

  158. 883666630

    Returns: 638083270

  159. 63509875

    Returns: 25493875

  160. 985539555

    Returns: 629709795

  161. 177518250

    Returns: 142267050

  162. 184749825

    Returns: 98591745

  163. 143198055

    Returns: 91496295

  164. 885851725

    Returns: 311464525

  165. 663918255

    Returns: 424210095

  166. 184756

    Returns: 115636

  167. 389025

    Returns: 233505

  168. 2147950

    Returns: 1491310

  169. 55709178

    Returns: 40631514

  170. 307716915

    Returns: 167311155

  171. 356425047

    Returns: 151799607

  172. 858599504

    Returns: 500575184

  173. 150

    Returns: 110

  174. 10000008

    Returns: 6666696

  175. 654987321

    Returns: 221471361

  176. 12494582

    Returns: 6252398

  177. 128

    Returns: 64

  178. 181336933

    Returns: 1

  179. 99999999

    Returns: 41247999

  180. 179424673

    Returns: 1

  181. 999999929

    Returns: 1

  182. 100000007

    Returns: 1

  183. 5100

    Returns: 3820

  184. 2512058

    Returns: 1256030

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: