Statistics

Problem Statement for "SumAndProduct"

Problem Statement

A list of non-negative numbers is called satisfactory if the sum of the numbers in the list is equal to S and the product of the numbers is equal to P. Find a satisfactory list with the least possible number of elements, and return its size. If no such list exists, return -1 instead. Please note that the list may contain non-integer numbers.

Definition

Class:
SumAndProduct
Method:
smallestSet
Parameters:
int, int
Returns:
int
Method signature:
int smallestSet(int S, int P)
(be sure your method is public)

Constraints

  • S and P will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 10

    10

    Returns: 1

    The list contains only one element: 10.

  2. 10

    20

    Returns: 2

  3. 10

    30

    Returns: 3

  4. 10

    34

    Returns: 3

  5. 10

    40

    Returns: -1

  6. 2

    3

    Returns: -1

  7. 5

    15

    Returns: -1

  8. 5

    7

    Returns: -1

  9. 33

    3333333

    Returns: -1

  10. 8

    256

    Returns: -1

  11. 90

    1000000000

    Returns: 9

  12. 13

    1333

    Returns: -1

  13. 76

    48828124

    Returns: 8

  14. 60

    60466175

    Returns: 10

  15. 60

    60476254

    Returns: 11

  16. 50

    69691719

    Returns: 15

  17. 30

    50805

    Returns: 9

  18. 10

    37

    Returns: 3

  19. 54

    387420489

    Returns: 18

  20. 2

    10

    Returns: -1

  21. 68

    552968336

    Returns: 12

  22. 501574537

    168

    Returns: 2

  23. 260733505

    123

    Returns: 2

  24. 176

    731260351

    Returns: 7

  25. 159

    349038653

    Returns: 7

  26. 178

    545

    Returns: 2

  27. 22101078

    56

    Returns: 2

  28. 85

    813890305

    Returns: 10

  29. 142

    753661427

    Returns: 7

  30. 104

    36813313

    Returns: 7

  31. 108

    935052470

    Returns: 8

  32. 216358530

    59

    Returns: 2

  33. 44

    987027754

    Returns: -1

  34. 63

    111127993

    Returns: 11

  35. 294366393

    73

    Returns: 2

  36. 161

    190595378

    Returns: 6

  37. 53

    92297437

    Returns: 14

  38. 74

    1925

    Returns: 3

  39. 4

    1727

    Returns: -1

  40. 437028657

    85

    Returns: 2

  41. 94

    632627638

    Returns: 9

  42. 73

    267515019

    Returns: 10

  43. 46

    742167708

    Returns: -1

  44. 18

    352700208

    Returns: -1

  45. 62

    11348479

    Returns: 8

  46. 893

    128

    Returns: 2

  47. 15

    754084469

    Returns: -1

  48. 559055798

    47

    Returns: 2

  49. 179

    125352733

    Returns: 6

  50. 178

    702476855

    Returns: 7

  51. 827156827

    247465052

    Returns: 2

  52. 197

    1033

    Returns: 2

  53. 256947828

    770

    Returns: 2

  54. 32304905

    757677834

    Returns: 2

  55. 765

    340992350

    Returns: 4

  56. 425850548

    785

    Returns: 2

  57. 1443

    93102370

    Returns: 3

  58. 203110238

    994773300

    Returns: 2

  59. 1635

    376530665

    Returns: 4

  60. 561

    772126853

    Returns: 5

  61. 873727942

    180782666

    Returns: 2

  62. 831965745

    947161312

    Returns: 2

  63. 1468658

    744

    Returns: 2

  64. 1309

    78610884

    Returns: 3

  65. 1575

    386164359

    Returns: 4

  66. 503672315

    345

    Returns: 2

  67. 300

    188016688

    Returns: 5

  68. 325020298

    851048036

    Returns: 2

  69. 495913889

    706869234

    Returns: 2

  70. 273253323

    312669917

    Returns: 2

  71. 40053118

    404

    Returns: 2

  72. 918461504

    908103053

    Returns: 2

  73. 398368799

    442

    Returns: 2

  74. 29150901

    819731125

    Returns: 2

  75. 943

    96751180

    Returns: 4

  76. 93011343

    990783761

    Returns: 2

  77. 376

    470347088

    Returns: 5

  78. 286

    85084726

    Returns: 5

  79. 904815917

    302202836

    Returns: 2

  80. 459334573

    642487918

    Returns: 2

  81. 718088328

    495208119

    Returns: 2

  82. 981574249

    626713388

    Returns: 2

  83. 239752737

    654835951

    Returns: 2

  84. 420317754

    771995929

    Returns: 2

  85. 116512458

    673157331

    Returns: 2

  86. 253191786

    301076386

    Returns: 2

  87. 698092704

    755690907

    Returns: 2

  88. 657995489

    676009395

    Returns: 2

  89. 581705076

    811828279

    Returns: 2

  90. 288025440

    459213433

    Returns: 2

  91. 442665519

    895037622

    Returns: 2

  92. 160467794

    716496406

    Returns: 2

  93. 27242347

    123054132

    Returns: 2

  94. 928077250

    247198559

    Returns: 2

  95. 687733114

    958261438

    Returns: 2

  96. 900182235

    140501888

    Returns: 2

  97. 15844541

    915940835

    Returns: 2

  98. 975

    953987377

    Returns: 4

  99. 52906374

    118081944

    Returns: 2

  100. 520448041

    669667622

    Returns: 2

  101. 290

    725648598

    Returns: 6

  102. 57

    1000000000

    Returns: 18

  103. 56

    1000000000

    Returns: -1

  104. 5

    6

    Returns: 2

    The list contains two elements: 2 and 3.

  105. 5

    100

    Returns: -1

    No such list exists.

  106. 100

    1000000000

    Returns: 9

  107. 90

    58077950

    Returns: 7

  108. 90

    58077951

    Returns: 8

  109. 82

    3

    Returns: 2

  110. 1000000000

    1

    Returns: 2

  111. 5

    1

    Returns: 2

  112. 11

    10

    Returns: 2

  113. 28

    1

    Returns: 2

  114. 12345678

    133

    Returns: 2

  115. 100

    10

    Returns: 2

  116. 567

    23472547

    Returns: 4

  117. 1000000000

    999999999

    Returns: 2

  118. 2

    1

    Returns: 2

  119. 25

    9

    Returns: 2

  120. 597125597

    868112354

    Returns: 2

  121. 1000000000

    999999937

    Returns: 2

  122. 20

    10

    Returns: 2

  123. 1000000000

    1000

    Returns: 2

  124. 1000000000

    2

    Returns: 2

  125. 900000000

    1000000000

    Returns: 2

  126. 6

    5

    Returns: 2

  127. 10

    1

    Returns: 2

  128. 999999999

    1000000000

    Returns: 2

  129. 39

    9621

    Returns: 5

  130. 999999991

    111123141

    Returns: 2

  131. 1000000000

    100

    Returns: 2

  132. 999999999

    1

    Returns: 2

  133. 4

    1

    Returns: 2

  134. 103

    216

    Returns: 2

  135. 62

    1000000000

    Returns: 14

  136. 8

    16

    Returns: 2

  137. 100

    1

    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: