Statistics

Problem Statement for "BestDecomposition"

Problem Statement

A decomposition of a non-negative integer n is a list of non-negative integers that sum to exactly n. The product of a decomposition is the product of all its members. For example, if n = 4, the following decompositions are possible:

4 = 1+1+1+1, product is 1*1*1*1 = 1.
4 = 1+1+2, product is 1*1*2 = 2.
4 = 1+3, product is 1*3 = 3.
4 = 2+2, product is 2*2 = 4.
4 = 4, product is 4.

Given an int n, determine the decomposition of n with the maximal product, and return that product modulo 10007. In the example above, the maximal product is 4 (the product of the decomposition 2 + 2).

Definition

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

Constraints

  • n will be between 0 and 10000, inclusive.

Examples

  1. 0

    Returns: 0

  2. 1

    Returns: 1

  3. 5

    Returns: 6

    5 = 2 + 3, 2 * 3 = 6

  4. 7

    Returns: 12

    7 = 3 + 4, 3 * 4 = 12

  5. 2

    Returns: 2

  6. 3

    Returns: 3

  7. 4

    Returns: 4

  8. 6

    Returns: 9

  9. 8

    Returns: 18

  10. 9

    Returns: 27

  11. 10

    Returns: 36

  12. 11

    Returns: 54

  13. 12

    Returns: 81

  14. 13

    Returns: 108

  15. 14

    Returns: 162

  16. 15

    Returns: 243

  17. 16

    Returns: 324

  18. 17

    Returns: 486

  19. 18

    Returns: 729

  20. 19

    Returns: 972

  21. 10000

    Returns: 9455

  22. 9999

    Returns: 9593

  23. 9998

    Returns: 9731

  24. 9997

    Returns: 9823

  25. 9996

    Returns: 9869

  26. 9995

    Returns: 9915

  27. 9994

    Returns: 6610

  28. 9993

    Returns: 9961

  29. 9992

    Returns: 3305

  30. 9991

    Returns: 5539

  31. 9990

    Returns: 6656

  32. 9989

    Returns: 7773

  33. 9988

    Returns: 5182

  34. 932

    Returns: 1300

  35. 284

    Returns: 3720

  36. 934

    Returns: 2600

  37. 992

    Returns: 7028

  38. 739

    Returns: 3675

  39. 74

    Returns: 8204

  40. 479

    Returns: 7329

  41. 520

    Returns: 9273

  42. 19

    Returns: 972

  43. 422

    Returns: 1954

  44. 4895

    Returns: 6634

  45. 4723

    Returns: 3967

  46. 4927

    Returns: 4095

  47. 5585

    Returns: 9940

  48. 4876

    Returns: 7016

  49. 5447

    Returns: 8425

  50. 5917

    Returns: 9771

  51. 5300

    Returns: 4270

  52. 4213

    Returns: 2314

  53. 5601

    Returns: 596

  54. 2129

    Returns: 1279

  55. 2570

    Returns: 6377

  56. 9253

    Returns: 9321

  57. 9936

    Returns: 1461

  58. 1658

    Returns: 5320

  59. 721

    Returns: 2270

  60. 9103

    Returns: 3392

  61. 107

    Returns: 7385

  62. 3042

    Returns: 9535

  63. 1721

    Returns: 3609

  64. 9969

    Returns: 726

  65. 9913

    Returns: 1887

  66. 9903

    Returns: 4222

  67. 9984

    Returns: 6299

  68. 9975

    Returns: 6534

  69. 9931

    Returns: 4664

  70. 9976

    Returns: 8712

  71. 9913

    Returns: 1887

  72. 9937

    Returns: 1948

  73. 9975

    Returns: 6534

  74. 9998

    Returns: 9731

  75. 9931

    Returns: 4664

  76. 9999

    Returns: 9593

  77. 10000

    Returns: 9455

  78. 9988

    Returns: 5182

  79. 9321

    Returns: 7004

  80. 9

    Returns: 27

  81. 6

    Returns: 9

  82. 573

    Returns: 3862

  83. 0

    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: