Statistics

Problem Statement for "Multifactorial"

Problem Statement

A multifactorial of a number is a generalization of the factorial function. The k-multifactorial of n is denoted by fack(n). The k-multifactorial of n is the product of every positive number of the form n - X*k, where X is a non-negative integer. For example, the 3-multifactorial of 14 is 14*11*8*5*2 = 12320, and the 4-multifactorial of 5 is 5*1 = 5.

A formal definition of multifactorial is:

  • fack(n) = n if k >= n
  • fack(n) = n*fack(n-k) if k < n

You will be given n and k and have to return the value of fack(n) as a String with no leading zeroes (this value is always a positive integer). If fack(n) is strictly greater than 1000000000000000000 (1018), return "overflow" (quotes for clarity) instead.

Definition

Class:
Multifactorial
Method:
calcMultiFact
Parameters:
int, int
Returns:
String
Method signature:
String calcMultiFact(int n, int k)
(be sure your method is public)

Notes

  • 1000000000000000000 (1018) fits in a long.

Constraints

  • n and k will each be between 1 and 2000000000 (2*109), inclusive.

Examples

  1. 14

    3

    Returns: "12320"

    The first example in the problem statement.

  2. 5

    4

    Returns: "5"

    The second example in the problem statement.

  3. 1000

    2

    Returns: "overflow"

    Way too big!

  4. 2000000000

    1900000000

    Returns: "200000000000000000"

  5. 1000

    256

    Returns: "84232704000"

  6. 1

    2000000000

    Returns: "1"

  7. 2000000000

    1

    Returns: "overflow"

  8. 999999999

    2452342

    Returns: "overflow"

  9. 20

    1

    Returns: "overflow"

  10. 21

    1

    Returns: "overflow"

  11. 500000000

    300000000

    Returns: "100000000000000000"

  12. 346534522

    234523499

    Returns: "38815686314036006"

  13. 1

    1

    Returns: "1"

  14. 1000000000

    500000000

    Returns: "500000000000000000"

  15. 1000000000

    499999999

    Returns: "overflow"

  16. 999999998

    499999998

    Returns: "999999998000000000"

  17. 2000000000

    1500000000

    Returns: "1000000000000000000"

  18. 1500000000

    749999996

    Returns: "overflow"

  19. 1500000000

    749999995

    Returns: "overflow"

  20. 2000000000

    1000000000

    Returns: "overflow"

  21. 19

    1

    Returns: "121645100408832000"

  22. 7096

    1665

    Returns: "132949364877520576"

  23. 1403

    240

    Returns: "92503795940503129"

  24. 580

    89

    Returns: "49844758346611200"

  25. 2883

    650

    Returns: "2690805827660643"

  26. 6765

    1565

    Returns: "133671026560500000"

  27. 789

    122

    Returns: "372592483175247615"

  28. 5740

    1053

    Returns: "overflow"

  29. 2032

    299

    Returns: "overflow"

  30. 9081

    1711

    Returns: "overflow"

  31. 2471

    441

    Returns: "overflow"

  32. 1299

    182

    Returns: "overflow"

  33. 788

    106

    Returns: "overflow"

  34. 44346642

    27276775

    Returns: "756991280836614"

  35. 514509426

    456665009

    Returns: "29761497787974642"

  36. 551970908

    468308461

    Returns: "46179236836091876"

  37. 58169460

    29439230

    Returns: "1671221964775800"

  38. 553651008

    357920486

    Returns: "108366400801666176"

  39. 71623417

    27276775

    Returns: "overflow"

  40. 971174435

    456665009

    Returns: "overflow"

  41. 1020279369

    468308461

    Returns: "overflow"

  42. 87608690

    29439230

    Returns: "overflow"

  43. 911571494

    357920486

    Returns: "overflow"

  44. 470471467

    383653989

    Returns: "40845146235900226"

  45. 1321684950

    1610906284

    Returns: "1321684950"

  46. 962668700

    1552320299

    Returns: "962668700"

  47. 1855938358

    1589679319

    Returns: "494160363644317962"

  48. 945693672

    1995299534

    Returns: "945693672"

  49. 1121829815

    510036533

    Returns: "overflow"

  50. 1085488572

    398983355

    Returns: "overflow"

  51. 1587268015

    837447602

    Returns: "overflow"

  52. 423332300

    165035639

    Returns: "overflow"

  53. 1930571740

    867298328

    Returns: "overflow"

  54. 1461315454

    531261815

    Returns: "overflow"

  55. 30

    2

    Returns: "42849873690624000"

  56. 111

    11

    Returns: "122087424094272000"

  57. 53

    4

    Returns: "885821206052908125"

  58. 637

    95

    Returns: "151534613656153728"

  59. 151

    16

    Returns: "532998118279051425"

  60. 338

    47

    Returns: "36814996368259200"

  61. 51

    4

    Returns: "178311467764705275"

  62. 213

    25

    Returns: "278761477374027648"

  63. 231

    27

    Returns: "642203484132672000"

  64. 78

    7

    Returns: "119715577952256000"

  65. 72

    6

    Returns: "overflow"

  66. 260

    31

    Returns: "overflow"

  67. 440

    57

    Returns: "overflow"

  68. 168

    16

    Returns: "overflow"

  69. 287

    31

    Returns: "overflow"

  70. 99

    9

    Returns: "overflow"

  71. 87

    7

    Returns: "overflow"

  72. 20

    1

    Returns: "overflow"

  73. 107

    9

    Returns: "overflow"

  74. 20

    1

    Returns: "overflow"

  75. 96

    10

    Returns: "9585618768101376"

  76. 59

    5

    Returns: "60705973649857536"

  77. 89

    8

    Returns: "494437513909964625"

  78. 89

    8

    Returns: "494437513909964625"

  79. 31

    2

    Returns: "191898783962510625"

  80. 70

    6

    Returns: "333247405883392000"

  81. 97

    10

    Returns: "13865696119905399"

  82. 62

    5

    Returns: "728640635326636032"

  83. 98

    9

    Returns: "886471860680806400"

  84. 78

    7

    Returns: "119715577952256000"

  85. 59

    5

    Returns: "60705973649857536"

  86. 19

    1

    Returns: "121645100408832000"

  87. 89

    8

    Returns: "494437513909964625"

  88. 30

    2

    Returns: "42849873690624000"

  89. 68

    6

    Returns: "73569236156416000"

  90. 74

    7

    Returns: "17921371792896000"

  91. 5

    5

    Returns: "5"

  92. 2000000000

    1

    Returns: "overflow"

  93. 200000000

    1

    Returns: "overflow"

  94. 669266210

    185904517

    Returns: "overflow"

  95. 2000000000

    1000000000

    Returns: "overflow"

  96. 1000000001

    499999999

    Returns: "overflow"

  97. 1000000000

    333333333

    Returns: "overflow"

  98. 200

    22

    Returns: "overflow"

  99. 1000000000

    400000000

    Returns: "overflow"

  100. 3

    3

    Returns: "3"

  101. 720

    100

    Returns: "overflow"

  102. 20

    1

    Returns: "overflow"

  103. 2000000000

    1500000000

    Returns: "1000000000000000000"

  104. 19

    1

    Returns: "121645100408832000"

  105. 25000000

    9992000

    Returns: "overflow"

  106. 305

    35

    Returns: "overflow"

  107. 1000000001

    500000000

    Returns: "500000001500000001"

  108. 6000

    1000

    Returns: "overflow"

  109. 4362252

    1454084

    Returns: "overflow"

  110. 1650966

    550322

    Returns: "overflow"

  111. 1000000000

    431987941

    Returns: "overflow"

  112. 100000000

    43987949

    Returns: "overflow"

  113. 110

    10

    Returns: "overflow"

  114. 261871898

    100333140

    Returns: "overflow"

  115. 200000000

    43809569

    Returns: "overflow"

  116. 1999999996

    1499999995

    Returns: "999999999999999996"

  117. 1000

    2

    Returns: "overflow"

  118. 5120

    1000

    Returns: "overflow"

  119. 1500000

    499000

    Returns: "overflow"

  120. 999000000

    425636850

    Returns: "overflow"

  121. 1000000000

    425636850

    Returns: "overflow"

  122. 1

    1

    Returns: "1"

  123. 281

    30

    Returns: "overflow"

  124. 2000000000

    1400000000

    Returns: "overflow"

  125. 2000000000

    639514741

    Returns: "overflow"

  126. 1000000000

    386822144

    Returns: "overflow"

  127. 1000

    96

    Returns: "overflow"

  128. 330000

    100000

    Returns: "overflow"

  129. 1999999999

    1500000000

    Returns: "999999997500000001"

  130. 130

    10

    Returns: "overflow"

  131. 1000000005

    499999993

    Returns: "overflow"

  132. 1000000005

    500000000

    Returns: "overflow"

  133. 999999999

    500000001

    Returns: "499999997500000002"

  134. 4

    10

    Returns: "4"

  135. 100000000

    1

    Returns: "overflow"

  136. 1000000000

    460000000

    Returns: "overflow"

  137. 1804289383

    846930886

    Returns: "overflow"

  138. 1671014630

    1066920525

    Returns: "overflow"

  139. 5

    1

    Returns: "120"

  140. 666

    88

    Returns: "overflow"

  141. 1000000000

    499999985

    Returns: "overflow"

  142. 1999999999

    1900000000

    Returns: "199999997900000001"

  143. 2000000000

    1499999999

    Returns: "overflow"

  144. 31

    2

    Returns: "191898783962510625"

  145. 100000

    25000

    Returns: "overflow"

  146. 33

    2

    Returns: "overflow"

  147. 1000000101

    500000000

    Returns: "overflow"

  148. 100

    10

    Returns: "36288000000000000"

  149. 1000000000

    333333300

    Returns: "overflow"

  150. 2000000000

    999999999

    Returns: "overflow"

  151. 158000000

    74000000

    Returns: "overflow"

  152. 18147702

    6049234

    Returns: "overflow"

  153. 15

    1

    Returns: "1307674368000"

  154. 900000000

    300000000

    Returns: "overflow"

  155. 1000000000

    390000000

    Returns: "overflow"

  156. 262144

    65536

    Returns: "overflow"

  157. 32

    2

    Returns: "overflow"

  158. 10

    10

    Returns: "10"

  159. 120000000

    40000000

    Returns: "overflow"

  160. 1000000002

    500000000

    Returns: "overflow"

  161. 10000000

    3333333

    Returns: "overflow"

  162. 16

    4

    Returns: "6144"

  163. 14

    14

    Returns: "14"

  164. 10000

    2

    Returns: "overflow"

  165. 100

    100

    Returns: "100"

  166. 2000000000

    1000000001

    Returns: "overflow"

  167. 2000000

    700000

    Returns: "overflow"

  168. 42

    2

    Returns: "overflow"

  169. 2

    1

    Returns: "2"

  170. 9

    3

    Returns: "162"

  171. 8

    1

    Returns: "40320"

  172. 43

    3

    Returns: "overflow"

  173. 2000000000

    100000005

    Returns: "overflow"

  174. 6

    3

    Returns: "18"

  175. 10

    1

    Returns: "3628800"

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: