Statistics

Problem Statement for "MyLongCake"

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:
MyLongCake
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 100,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

  3. 15

    Returns: 7

    You are expecting 1, 3, or 5 friends.

  4. 12

    Returns: 8

  5. 100000

    Returns: 60000

  6. 21169

    Returns: 1

  7. 43905

    Returns: 20497

  8. 22106

    Returns: 12638

  9. 74789

    Returns: 12149

  10. 65822

    Returns: 32912

  11. 99027

    Returns: 33015

  12. 79588

    Returns: 40388

  13. 25790

    Returns: 15478

  14. 13744

    Returns: 6880

  15. 30878

    Returns: 15440

  16. 41101

    Returns: 1809

  17. 54039

    Returns: 18015

  18. 71899

    Returns: 1

  19. 99064

    Returns: 58744

  20. 77676

    Returns: 51788

  21. 2

    Returns: 1

  22. 100000

    Returns: 60000

  23. 3

    Returns: 1

  24. 99999

    Returns: 35199

  25. 4

    Returns: 2

  26. 99998

    Returns: 50000

  27. 5

    Returns: 1

  28. 99997

    Returns: 5605

  29. 6

    Returns: 4

  30. 99996

    Returns: 69276

  31. 7

    Returns: 1

  32. 99995

    Returns: 31451

  33. 8

    Returns: 4

  34. 99994

    Returns: 53210

  35. 9

    Returns: 3

  36. 99993

    Returns: 33333

  37. 10

    Returns: 6

  38. 99992

    Returns: 51832

  39. 11

    Returns: 1

  40. 99991

    Returns: 1

  41. 2

    Returns: 1

  42. 65536

    Returns: 32768

  43. 3

    Returns: 1

  44. 59049

    Returns: 19683

  45. 5

    Returns: 1

  46. 78125

    Returns: 15625

  47. 7

    Returns: 1

  48. 16807

    Returns: 2401

  49. 11

    Returns: 1

  50. 14641

    Returns: 1331

  51. 23

    Returns: 1

  52. 12167

    Returns: 529

  53. 53

    Returns: 1

  54. 2809

    Returns: 53

  55. 113

    Returns: 1

  56. 12769

    Returns: 113

  57. 271

    Returns: 1

  58. 73441

    Returns: 271

  59. 997

    Returns: 1

  60. 4001

    Returns: 1

  61. 9973

    Returns: 1

  62. 10301

    Returns: 1

  63. 31607

    Returns: 1

  64. 99991

    Returns: 1

  65. 2

    Returns: 1

  66. 6

    Returns: 4

  67. 30

    Returns: 22

  68. 210

    Returns: 162

  69. 2310

    Returns: 1830

  70. 30030

    Returns: 24270

  71. 85085

    Returns: 39005

  72. 46189

    Returns: 11629

  73. 9973

    Returns: 1

  74. 10007

    Returns: 1

  75. 99991

    Returns: 1

  76. 31607

    Returns: 1

  77. 33331

    Returns: 1

  78. 65

    Returns: 17

  79. 60042

    Returns: 40030

  80. 10

    Returns: 6

  81. 7

    Returns: 1

  82. 9973

    Returns: 1

  83. 147

    Returns: 63

  84. 31607

    Returns: 1

  85. 13

    Returns: 1

  86. 9973

    Returns: 1

  87. 17

    Returns: 1

  88. 64800

    Returns: 47520

  89. 33750

    Returns: 24750

  90. 43200

    Returns: 31680

  91. 33750

    Returns: 24750

  92. 33750

    Returns: 24750

  93. 97200

    Returns: 71280

  94. 54000

    Returns: 39600

  95. 40500

    Returns: 29700

  96. 22500

    Returns: 16500

  97. 21600

    Returns: 15840

  98. 44100

    Returns: 34020

  99. 99225

    Returns: 53865

  100. 56700

    Returns: 43740

  101. 52920

    Returns: 40824

  102. 61740

    Returns: 47628

  103. 91875

    Returns: 49875

  104. 15750

    Returns: 12150

  105. 88200

    Returns: 68040

  106. 44100

    Returns: 34020

  107. 55566

    Returns: 39690

  108. 30800

    Returns: 21200

  109. 64680

    Returns: 51240

  110. 9240

    Returns: 7320

  111. 79200

    Returns: 60000

  112. 63525

    Returns: 37125

  113. 33880

    Returns: 23320

  114. 82320

    Returns: 63504

  115. 11858

    Returns: 7238

  116. 35640

    Returns: 27000

  117. 59895

    Returns: 30855

  118. 28561

    Returns: 2197

  119. 22815

    Returns: 11583

  120. 68750

    Returns: 43750

  121. 15015

    Returns: 9255

  122. 80850

    Returns: 64050

  123. 10890

    Returns: 8250

  124. 28028

    Returns: 17948

  125. 25025

    Returns: 10625

  126. 81120

    Returns: 61152

  127. 60060

    Returns: 48540

  128. 78540

    Returns: 63180

  129. 42350

    Returns: 29150

  130. 10010

    Returns: 7130

  131. 22950

    Returns: 17190

  132. 88434

    Returns: 60690

  133. 57330

    Returns: 45234

  134. 42075

    Returns: 22875

  135. 28050

    Returns: 21650

  136. 75140

    Returns: 49028

  137. 9438

    Returns: 6798

  138. 30940

    Returns: 21724

  139. 20995

    Returns: 7171

  140. 24225

    Returns: 12705

  141. 83160

    Returns: 65880

  142. 71383

    Returns: 12631

  143. 36465

    Returns: 21105

  144. 92055

    Returns: 48279

  145. 46189

    Returns: 11629

  146. 41327

    Returns: 8687

  147. 17689

    Returns: 3325

  148. 99730

    Returns: 59842

  149. 29478

    Returns: 20230

  150. 58956

    Returns: 40460

  151. 48906

    Returns: 35946

  152. 13

    Returns: 1

  153. 51051

    Returns: 28011

  154. 13500

    Returns: 9900

  155. 30345

    Returns: 17289

  156. 69811

    Returns: 9979

  157. 57057

    Returns: 31137

  158. 90090

    Returns: 72810

  159. 28342

    Returns: 14590

  160. 48986

    Returns: 27998

  161. 120

    Returns: 88

  162. 33

    Returns: 13

  163. 105

    Returns: 57

  164. 60

    Returns: 44

  165. 91234

    Returns: 54274

  166. 49

    Returns: 7

  167. 42389

    Returns: 4373

  168. 20014

    Returns: 10008

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: