Statistics

Problem Statement for "SetMultiples"

Problem Statement

Suppose that S1 and S2 are sets of integer numbers. Let's call S2 a multiple of S1 if for each integer x from S1 there exist an integer y from S2 such that y is an integer multiple of x, i.e., y = k * x, where k is an integer.

You are given longs A, B, C, D. Consider a set S consisting of integers x such that A <= x <= B or C <= x <= D. Return the number of elements in the smallest subset of S that is a multiple of S.

Definition

Class:
SetMultiples
Method:
smallestSubset
Parameters:
long, long, long, long
Returns:
long
Method signature:
long smallestSubset(long A, long B, long C, long D)
(be sure your method is public)

Notes

  • Since S is a subset of S and S is a multiple of S, the answer exists for any test case.

Constraints

  • A will be between 1 and 10,000,000,000, inclusive.
  • B will be between A and 10,000,000,000, inclusive.
  • C will be between B + 1 and 10,000,000,000, inclusive.
  • D will be between C and 10,000,000,000, inclusive.

Examples

  1. 1

    1

    2

    2

    Returns: 1

    Here S = {1, 2}. The subset {2} is a multiple of S because 2 is a multiple of both 1 and 2.

  2. 1

    2

    3

    4

    Returns: 2

    This time, S = {1, 2, 3, 4}. The subset {3, 4} is a multiple of S because 4 is a multiple of 1, 2 and 4, and 3 is a multiple of 3.

  3. 2

    3

    5

    7

    Returns: 3

    S = {2, 3, 5, 6, 7}. The solution is {5, 6, 7}.

  4. 1

    10

    100

    1000

    Returns: 500

  5. 1000000000

    2000000000

    9000000000

    10000000000

    Returns: 1254365078

  6. 41

    29233

    576686

    6194477512

    Returns: 3097238756

  7. 53243

    11124726

    10000000000

    10000000000

    Returns: 5562359

  8. 9

    4261

    10000000000

    10000000000

    Returns: 2127

  9. 1

    1

    3

    3

    Returns: 1

  10. 2

    2

    3

    4

    Returns: 2

  11. 3

    3

    7

    7

    Returns: 2

  12. 2

    2

    5

    7

    Returns: 3

  13. 12805

    4631846

    38028364

    53266554

    Returns: 15238191

  14. 4926

    29891015

    45714433

    54336151

    Returns: 16382462

  15. 456

    703902

    6796533

    6489268619

    Returns: 3244634310

  16. 5

    360797

    3434567022

    10000000000

    Returns: 5000000000

  17. 4

    274234

    10000000000

    10000000000

    Returns: 137114

  18. 8

    146087

    10000000000

    10000000000

    Returns: 73040

  19. 7100

    175791

    10000000000

    10000000000

    Returns: 87892

  20. 92072

    249633

    10000000000

    10000000000

    Returns: 124813

  21. 34849

    167031

    80928382

    4962617292

    Returns: 2481308646

  22. 2

    9

    25

    29

    Returns: 7

  23. 5

    32084

    6259720

    11817150

    Returns: 5557431

  24. 399

    9680

    557942

    8059374

    Returns: 4029687

  25. 223

    18630

    75732

    384696

    Returns: 192348

  26. 73

    543

    763

    837

    Returns: 302

  27. 7

    15

    114

    345

    Returns: 173

  28. 4

    6

    79

    212

    Returns: 106

  29. 1

    91

    751

    78334

    Returns: 39167

  30. 1

    6

    3993

    579438

    Returns: 289719

  31. 266

    9741

    98451

    1783049

    Returns: 891525

  32. 8

    17

    90

    165

    Returns: 76

  33. 3

    278

    738

    9936

    Returns: 4968

  34. 26

    887

    4830

    433803

    Returns: 216902

  35. 9

    21

    41

    65

    Returns: 25

  36. 3

    11

    96

    21032

    Returns: 10516

  37. 1

    1

    4

    4

    Returns: 1

  38. 9

    9

    470

    9911

    Returns: 4956

  39. 43

    82

    242

    416

    Returns: 175

  40. 4

    4

    5

    50

    Returns: 25

  41. 4

    7

    17

    25

    Returns: 9

  42. 5

    84

    211

    940

    Returns: 470

  43. 86

    8154

    9139023

    9781964

    Returns: 642942

  44. 1

    8

    11220

    47314

    Returns: 23657

  45. 2

    52

    95

    706

    Returns: 353

  46. 2

    4

    6

    850

    Returns: 425

  47. 9

    289

    844

    882

    Returns: 155

  48. 1

    47

    95

    458

    Returns: 229

  49. 20

    48

    300

    253151

    Returns: 126576

  50. 4

    4

    5

    6448

    Returns: 3224

  51. 7

    1311

    176463

    8008135

    Returns: 4004068

  52. 86

    76351

    5664046

    28153745

    Returns: 14076873

  53. 1

    1

    2

    5

    Returns: 3

  54. 43

    396

    6559187

    7066419

    Returns: 507233

  55. 60

    8450

    9760

    96340130

    Returns: 48170065

  56. 2

    7

    37

    90

    Returns: 45

  57. 6558

    816765

    896501

    9632905

    Returns: 4816453

  58. 85

    23716

    82080

    17981309

    Returns: 8990655

  59. 1706

    3412

    6639

    105379

    Returns: 52690

  60. 1

    15

    67

    1141

    Returns: 571

  61. 3

    8

    72

    162

    Returns: 81

  62. 6

    9

    10

    21

    Returns: 11

  63. 1948

    294799

    312363

    564312

    Returns: 264593

  64. 3

    4

    5

    7

    Returns: 4

  65. 9

    83

    754

    810

    Returns: 62

  66. 1

    3

    7

    8

    Returns: 3

  67. 5

    9

    16

    16

    Returns: 5

  68. 75

    152

    280

    366

    Returns: 106

  69. 13

    75

    78

    89

    Returns: 44

  70. 832397

    16489674

    55866960

    66771211

    Returns: 11561605

  71. 4

    9895

    94668

    98542

    Returns: 6038

  72. 4

    54

    56

    63

    Returns: 31

  73. 2

    3

    4

    5

    Returns: 3

  74. 6

    301

    489

    505

    Returns: 154

  75. 5490

    145509

    839332

    910116

    Returns: 94492

  76. 3

    11

    16

    18

    Returns: 6

  77. 2

    869

    74111

    74249

    Returns: 484

  78. 78219

    731561

    872441

    980001

    Returns: 419562

  79. 1

    769

    7314

    7684

    Returns: 489

  80. 2

    3

    8

    8

    Returns: 2

  81. 1

    4

    7

    8

    Returns: 3

  82. 6

    37

    38

    73

    Returns: 37

  83. 32

    44

    77

    82

    Returns: 16

  84. 1

    3

    4

    5

    Returns: 3

  85. 3

    14072305

    59985707

    69522369

    Returns: 10180425

  86. 39

    92

    10000000000

    10000000000

    Returns: 44

  87. 5

    47

    59

    84

    Returns: 32

  88. 77495

    5460792

    10000000000

    10000000000

    Returns: 2730392

  89. 374

    71396

    10000000000

    10000000000

    Returns: 35695

  90. 20

    33

    48

    57

    Returns: 19

  91. 79

    494

    504

    760

    Returns: 371

  92. 517613

    2562520720

    10000000000

    10000000000

    Returns: 1281260359

  93. 1

    5

    7

    8

    Returns: 4

  94. 7

    996415

    4023784

    4910097

    Returns: 900710

  95. 9

    25

    64

    74

    Returns: 16

  96. 2

    3

    4

    5

    Returns: 3

  97. 56031

    7497093

    8888606

    9411287

    Returns: 4009888

  98. 5

    7

    47

    49

    Returns: 4

  99. 419

    1197

    2855

    3073

    Returns: 674

  100. 1

    3

    9

    9

    Returns: 2

  101. 1

    4

    5

    6

    Returns: 3

  102. 8

    9

    41

    45

    Returns: 6

  103. 84184

    250545

    58547583

    10000000000

    Returns: 5000000000

  104. 41

    65

    8759509

    10000000000

    Returns: 5000000000

  105. 433044

    26578961

    6077706340

    10000000000

    Returns: 3922293661

  106. 80

    2479063899

    10000000000

    10000000000

    Returns: 1239531949

  107. 5677

    3318457959

    10000000000

    10000000000

    Returns: 1659228979

  108. 6

    16631

    32758084

    10000000000

    Returns: 5000000000

  109. 160093

    48951514

    368024267

    10000000000

    Returns: 5000000000

  110. 206582

    6579518

    92710377

    10000000000

    Returns: 5000000000

  111. 61

    9257

    4248597828

    10000000000

    Returns: 5000000000

  112. 521284

    9317959

    10000000000

    10000000000

    Returns: 4658977

  113. 520

    6953888011

    9999992314

    10000000000

    Returns: 3476947849

  114. 65

    86697863

    9999912175

    10000000000

    Returns: 43376072

  115. 295655408

    9976567757

    9999999819

    10000000000

    Returns: 4988283970

  116. 857947599

    6158681407

    8627634266

    10000000000

    Returns: 3511530941

  117. 311

    9999999634

    9999999912

    10000000000

    Returns: 4999999861

  118. 2332065633

    9999999523

    9999999946

    10000000000

    Returns: 4999999789

  119. 6416747

    9992145680

    9999927048

    10000000000

    Returns: 4996109316

  120. 4

    7774581097

    9999993819

    10000000000

    Returns: 3887293640

  121. 7370

    3881691265

    9999999995

    10000000000

    Returns: 1940845633

  122. 5668543

    5983679057

    9910634386

    10000000000

    Returns: 3006733798

  123. 4

    9999924646

    9999999586

    10000000000

    Returns: 4999962530

  124. 896873313

    9999992405

    9999999998

    10000000000

    Returns: 4999996204

  125. 9692

    9699483596

    9999947326

    10000000000

    Returns: 4849768135

  126. 95

    756

    9999999340

    10000000000

    Returns: 665

  127. 600100

    649475

    9999991764

    10000000000

    Returns: 56968

  128. 93104565

    9999976247

    9999999996

    10000000000

    Returns: 4999988126

  129. 488

    9946305857

    9999512107

    10000000000

    Returns: 4973396876

  130. 1854448083

    4466549838

    9999958007

    10000000000

    Returns: 2233292416

  131. 7360

    6829002915

    9999967453

    10000000000

    Returns: 3414517732

  132. 151222

    363806

    9999973086

    10000000000

    Returns: 190055

  133. 594487

    36194357

    9999999696

    10000000000

    Returns: 18097280

  134. 921963

    9993426083

    9999918144

    10000000000

    Returns: 4996753970

  135. 93849413

    9999878597

    9999998511

    10000000000

    Returns: 4999940044

  136. 99

    9999038307

    9999992805

    10000000000

    Returns: 4999522752

  137. 67792

    9999999974

    9999999997

    10000000000

    Returns: 4999999989

  138. 45

    58

    9999999994

    10000000000

    Returns: 19

  139. 67282004

    9999559485

    9999999966

    10000000000

    Returns: 4999779760

  140. 958330

    9978975265

    9999993417

    10000000000

    Returns: 4989490925

  141. 4651742

    6244717215

    9994730096

    10000000000

    Returns: 3123236925

  142. 268405

    9999612732

    9999999965

    10000000000

    Returns: 4999806384

  143. 5000000000

    7000000000

    8000000000

    10000000000

    Returns: 4000000001

  144. 1

    100

    5000000000

    10000000000

    Returns: 5000000000

  145. 1

    100000

    777777777

    777777777

    Returns: 50001

  146. 1

    5000000000

    5000000002

    10000000000

    Returns: 4999999999

  147. 7

    7

    6000000000

    10000000000

    Returns: 4000000001

  148. 1

    2

    9000000000

    10000000000

    Returns: 1000000001

  149. 1

    13

    66

    69

    Returns: 10

  150. 1

    9999999998

    9999999999

    10000000000

    Returns: 5000000000

  151. 1

    1000000000

    1000000007

    1000000007

    Returns: 500000001

  152. 1

    200

    9000000000

    10000000000

    Returns: 1000000001

  153. 1

    2

    10000000000

    10000000000

    Returns: 1

  154. 2

    3

    4

    10000000000

    Returns: 5000000000

  155. 44444444

    55555555

    9999990000

    9999999999

    Returns: 11118874

  156. 1

    1

    9999999990

    10000000000

    Returns: 11

  157. 1

    799

    800

    1000

    Returns: 500

  158. 39

    72

    870

    913

    Returns: 51

  159. 1

    9900000000

    9999000000

    10000000000

    Returns: 4950500000

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: