Statistics

Problem Statement for "ConcatenateNumber"

Problem Statement

Given a positive integer number, concatenate one or more copies of number to create an integer that is divisible by k. Do not add any leading zeroes. Return the least number of copies needed, or -1 if it is impossible.

Definition

Class:
ConcatenateNumber
Method:
getSmallest
Parameters:
int, int
Returns:
int
Method signature:
int getSmallest(int number, int k)
(be sure your method is public)

Constraints

  • number will be between 1 and 1,000,000,000, inclusive.
  • k will be between 1 and 100,000, inclusive.

Examples

  1. 2

    9

    Returns: 9

    At least 9 copies are needed, since 222222222 is divisible by 9.

  2. 121

    11

    Returns: 1

    121 is divisible by 11.

  3. 1

    2

    Returns: -1

    You can never get an even number by concatenating only 1's.

  4. 1000000000

    6

    Returns: 3

  5. 1000000000

    7

    Returns: 3

  6. 35

    98765

    Returns: 9876

    The resulting integer could be really big.

  7. 987654321

    744

    Returns: -1

  8. 987654320

    744

    Returns: 15

  9. 1000000000

    3

    Returns: 3

  10. 1000000000

    9

    Returns: 9

  11. 80606847

    2

    Returns: -1

  12. 797790

    4830

    Returns: 11

  13. 96927

    146

    Returns: -1

  14. 6458346

    8865

    Returns: -1

  15. 69327745

    505

    Returns: 101

  16. 4368969

    158

    Returns: -1

  17. 35684892

    80

    Returns: -1

  18. 8629502

    391

    Returns: 176

  19. 210095368

    9006

    Returns: 78

  20. 18170

    175

    Returns: -1

  21. 537502

    42071

    Returns: 601

  22. 27419065

    1558

    Returns: -1

  23. 19645297

    40

    Returns: -1

  24. 16295560

    129

    Returns: 21

  25. 12302098

    349

    Returns: 29

  26. 1418026

    5

    Returns: -1

  27. 2648106

    560

    Returns: -1

  28. 6013204

    37374

    Returns: 2076

  29. 53662629

    115

    Returns: -1

  30. 44276444

    11910

    Returns: -1

  31. 1519484

    215

    Returns: -1

  32. 377468

    1474

    Returns: 11

  33. 11413325

    4559

    Returns: 276

  34. 32240004

    2138

    Returns: 267

  35. 29745952

    597

    Returns: 99

  36. 21289069

    8000

    Returns: -1

  37. 354221

    4344

    Returns: -1

  38. 82482383

    560

    Returns: -1

  39. 48763562

    10643

    Returns: 1281

  40. 669635470

    14646

    Returns: 915

  41. 347936059

    80935

    Returns: -1

  42. 177277052

    79536

    Returns: -1

  43. 87080248

    72066

    Returns: 18015

  44. 304141205

    70030

    Returns: -1

  45. 9603615

    71206

    Returns: -1

  46. 10887136

    57794

    Returns: 1155

  47. 135419645

    74183

    Returns: 920

  48. 253800410

    4034

    Returns: 224

  49. 175323350

    18661

    Returns: 6220

  50. 359633029

    85788

    Returns: -1

  51. 623823570

    66459

    Returns: 7384

  52. 10136071

    3000

    Returns: -1

  53. 416829220

    20526

    Returns: 930

  54. 129696078

    65981

    Returns: 65980

  55. 25789568

    20306

    Returns: 1155

  56. 220619407

    99624

    Returns: -1

  57. 34844860

    51010

    Returns: 425

  58. 268837226

    90822

    Returns: 45408

  59. 10899108

    44559

    Returns: 2475

  60. 200925606

    60162

    Returns: 185

  61. 436861970

    92427

    Returns: 11553

  62. 771198350

    63478

    Returns: 4976

  63. 162866350

    95699

    Returns: 5248

  64. 768381436

    20912

    Returns: -1

  65. 191827828

    69173

    Returns: 208

  66. 110243440

    51181

    Returns: 14

  67. 84809191

    91585

    Returns: -1

  68. 346093272

    92978

    Returns: 3874

  69. 328160962

    55277

    Returns: 9130

  70. 1

    1

    Returns: 1

  71. 1

    111

    Returns: 3

  72. 976342277

    23433

    Returns: 1272

  73. 1387951

    77771

    Returns: 38376

  74. 1000002

    10000

    Returns: -1

  75. 981249812

    15124

    Returns: 22

  76. 763481

    73499

    Returns: 6028

  77. 99999

    50001

    Returns: 1428

  78. 987654321

    99877

    Returns: 16646

  79. 999989999

    99999

    Returns: 45

  80. 1

    19683

    Returns: 19683

  81. 22

    4

    Returns: -1

  82. 10

    110

    Returns: 11

  83. 1000000000

    99999

    Returns: 99999

  84. 50000

    50001

    Returns: 1428

  85. 1

    5

    Returns: -1

  86. 999999997

    99997

    Returns: 874

  87. 123456787

    1234

    Returns: -1

  88. 891659132

    82731

    Returns: 132

  89. 842379391

    87393

    Returns: 29130

  90. 999999999

    97327

    Returns: 10814

  91. 2

    4

    Returns: -1

  92. 1000000000

    97653

    Returns: 189

  93. 4

    5

    Returns: -1

  94. 354

    98765

    Returns: -1

  95. 12345

    50021

    Returns: 10004

  96. 10

    10

    Returns: 1

  97. 10

    101

    Returns: 2

  98. 910000009

    93333

    Returns: 11427

  99. 999999999

    99991

    Returns: 5555

  100. 1000000000

    32147

    Returns: 24

  101. 37

    35867

    Returns: 330

  102. 977745435

    98757

    Returns: 8229

  103. 100000000

    98798

    Returns: 784

  104. 11

    2

    Returns: -1

  105. 987654324

    89766

    Returns: 831

  106. 100090000

    99991

    Returns: 5555

  107. 3

    4

    Returns: -1

  108. 1000000000

    10007

    Returns: 5003

  109. 20

    1000

    Returns: -1

  110. 1000000000

    99700

    Returns: 83

  111. 999999997

    98311

    Returns: 46256

  112. 11

    11

    Returns: 1

  113. 17

    5

    Returns: -1

  114. 10000000

    19683

    Returns: 19683

  115. 11

    121

    Returns: 11

  116. 1

    100

    Returns: -1

  117. 2

    100000

    Returns: -1

  118. 910000019

    93333

    Returns: 11427

  119. 353

    98765

    Returns: -1

  120. 100000001

    96875

    Returns: -1

  121. 10

    11

    Returns: 11

  122. 10

    1010

    Returns: 2

  123. 3

    2

    Returns: -1

  124. 100010000

    100000

    Returns: -1

  125. 100000

    87654

    Returns: 3129

  126. 999999999

    100000

    Returns: -1

  127. 10

    12345

    Returns: 411

  128. 1000000000

    70639

    Returns: 35319

  129. 13

    1313

    Returns: 2

  130. 998789456

    99447

    Returns: 99444

  131. 1000000000

    81387

    Returns: 13563

  132. 10

    8

    Returns: -1

  133. 100

    1001

    Returns: 2

  134. 1

    6

    Returns: -1

  135. 11

    30

    Returns: -1

  136. 99998

    99999

    Returns: 99999

  137. 10

    7

    Returns: 3

  138. 9998

    9999

    Returns: 9999

  139. 100

    33

    Returns: 6

  140. 474741

    5

    Returns: -1

  141. 22

    10

    Returns: -1

  142. 1000000000

    65537

    Returns: 32768

  143. 13

    11

    Returns: 11

  144. 5

    15

    Returns: 3

  145. 3

    5

    Returns: -1

  146. 7

    5

    Returns: -1

  147. 1

    98765

    Returns: -1

  148. 1

    100000

    Returns: -1

  149. 10000

    99999

    Returns: 99999

  150. 2

    15

    Returns: -1

  151. 1

    12

    Returns: -1

  152. 34

    56

    Returns: -1

  153. 2

    7

    Returns: 6

  154. 1000000000

    97283

    Returns: 48641

  155. 3

    25

    Returns: -1

  156. 111111111

    99998

    Returns: -1

  157. 65536

    66000

    Returns: -1

  158. 10

    98765

    Returns: 9876

  159. 150

    12

    Returns: -1

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: