Statistics

Problem Statement for "SecondLargestMultiple"

Problem Statement

In this problem we are interested in non-negative integers that have all digits distinct. For example, in base 10 the numbers 0, 47, 74, 13579, and 9876543201 all have this property.

The number 114 does not have this property in base 10, but it does have it in base 4 (where its digits are 1302).


You are given a positive integer N and the base B.

Let S(N,B) be the set of all non-negative integers that are multiples of N and have all digits distinct. Find and return the second largest number in S(N,B). If there is no such number, return -1 instead.

Definition

Class:
SecondLargestMultiple
Method:
find
Parameters:
long, int
Returns:
long
Method signature:
long find(long N, int B)
(be sure your method is public)

Constraints

  • N will be between 1 and 10^18, inclusive.
  • B will be between 2 and 12, inclusive.

Examples

  1. 1

    10

    Returns: 9876543201

    We are in base 10. The largest multiple of 1 with distinct digits is clearly 9876543210, and the second largest is 9876543201.

  2. 12345

    10

    Returns: 9876012345

  3. 12345

    3

    Returns: -1

  4. 2

    2

    Returns: 0

    The largest non-negative integer that has distinct digits in base 2 is 10 (base 2) = 2 (base 10). This is a multiple of 2, so it's the largest integer in S(2,2). The next non-negative integer that has distinct digits in base 2 is 1 (base 2) = 1 (base 10). This is not a multiple of 2. The final non-negative integer that has distinct digits in base 2 is 0 (base 2) = 0 (base 10). This is a multiple of 2 and thus the number we seek.

  5. 17

    4

    Returns: -1

    The only multiple of 17 that has distinct digits in base-4 is the number 0. Thus, the second largest number with this property does not exist.

  6. 282458553905

    11

    Returns: 0

    The only two multiples of this N with distinct digits in base 11 are zero and itself.

  7. 25

    7

    Returns: 800025

  8. 1768001

    12

    Returns: 8810065671066

    This runs for about one second if I don't break the distinct digit test early, so anything with less than 5_000_000 multiples should run in time.

  9. 1628712

    12

    Returns: 736759274184

    This one seemingly should have a pandigital solution but doesn't. The correct answer is 736759274184 = ba957234860_12.

  10. 497666

    12

    Returns: -1

  11. 746499

    12

    Returns: -1

  12. 1628797

    12

    Returns: 8226071482409

  13. 791738

    12

    Returns: 8655670142834

  14. 161052

    11

    Returns: -1

  15. 161062

    11

    Returns: -1

  16. 14642

    11

    Returns: 23073156440

  17. 43926

    11

    Returns: 23034047658

  18. 222

    11

    Returns: 25677847782

  19. 223

    11

    Returns: 282456457355

  20. 382

    11

    Returns: 25677554860

  21. 591

    11

    Returns: 282452714625

  22. 888

    11

    Returns: 25676099088

  23. 1047

    11

    Returns: 282428244765

  24. 2291

    11

    Returns: 282412612405

  25. 2660

    11

    Returns: 25651728620

  26. 2

    11

    Returns: 25678050334

  27. 1330

    11

    Returns: 25657065910

  28. 3137

    11

    Returns: 282341967655

  29. 5320

    11

    Returns: 25651114160

  30. 5521

    11

    Returns: 282312994795

  31. 6016

    11

    Returns: 25645558272

  32. 8544

    11

    Returns: 25630086144

  33. 9833

    11

    Returns: 282024943675

  34. 11376

    11

    Returns: 25614622512

  35. 14642

    11

    Returns: 23073156440

  36. 12216

    11

    Returns: 25612835208

  37. 13199

    11

    Returns: 281894540735

  38. 700

    10

    Returns: -1

  39. 1234700

    10

    Returns: -1

  40. 248833

    12

    Returns: -1

  41. 32

    9

    Returns: 42372480

  42. 33

    9

    Returns: 381352620

  43. 8

    9

    Returns: 42373288

  44. 9

    9

    Returns: 381366972

  45. 7

    9

    Returns: 381364788

  46. 47

    7

    Returns: 795099

  47. 48

    7

    Returns: 112176

  48. 49

    7

    Returns: -1

  49. 107

    6

    Returns: 39590

  50. 108

    6

    Returns: -1

  51. 77

    6

    Returns: 16555

  52. 225

    5

    Returns: -1

  53. 28

    5

    Returns: 420

  54. 29

    5

    Returns: 1914

  55. 30

    5

    Returns: 2790

  56. 3

    4

    Returns: 225

  57. 23

    4

    Returns: -1

  58. 78

    4

    Returns: 78

  59. 2638

    5

    Returns: 0

  60. 3

    3

    Returns: 15

  61. 4

    3

    Returns: -1

  62. 6

    3

    Returns: 0

  63. 18

    3

    Returns: -1

  64. 19

    3

    Returns: 0

  65. 7

    3

    Returns: 7

  66. 1

    2

    Returns: 1

  67. 3

    2

    Returns: -1

  68. 1

    11

    Returns: 282458553895

  69. 1

    12

    Returns: 8842413667681

  70. 7

    10

    Returns: 9876543012

  71. 7

    11

    Returns: 282458552355

  72. 7

    12

    Returns: 8842413664392

  73. 32

    9

    Returns: 42372480

  74. 31

    9

    Returns: 381313764

  75. 4961

    11

    Returns: -1

  76. 343

    7

    Returns: -1

  77. 5

    9

    Returns: 381365580

  78. 3

    9

    Returns: 381366972

  79. 22

    9

    Returns: 381364940

  80. 26

    9

    Returns: 381365660

  81. 56

    9

    Returns: 42371112

  82. 63

    9

    Returns: 381359916

  83. 168

    9

    Returns: 42371112

  84. 146

    9

    Returns: 381361052

  85. 505

    9

    Returns: 380772020

  86. 440

    9

    Returns: 42357920

  87. 1532

    9

    Returns: 379275708

  88. 1989

    9

    Returns: 379525068

  89. 2522

    9

    Returns: 380534492

  90. 5615

    9

    Returns: 379012500

  91. 17351

    9

    Returns: 349587948

  92. 6948

    9

    Returns: 376866468

  93. 26397

    9

    Returns: 366918300

  94. 19724

    9

    Returns: 374144556

  95. 93626

    9

    Returns: 329750772

  96. 162890

    9

    Returns: 0

  97. 429619

    9

    Returns: 4296190

  98. 463768

    9

    Returns: -1

  99. 550600

    9

    Returns: -1

  100. 1193255

    9

    Returns: 0

  101. 3974876

    9

    Returns: 0

  102. 3388224

    9

    Returns: -1

  103. 8642516

    9

    Returns: -1

  104. 8771615

    9

    Returns: -1

  105. 31906921

    9

    Returns: -1

  106. 31594299

    9

    Returns: -1

  107. 91241906

    9

    Returns: -1

  108. 102400618

    9

    Returns: -1

  109. 4

    10

    Returns: 9876543012

  110. 3

    10

    Returns: 9876543201

  111. 26

    10

    Returns: 9876523410

  112. 20

    10

    Returns: 9876541320

  113. 72

    10

    Returns: 9876541320

  114. 71

    10

    Returns: 9876453012

  115. 171

    10

    Returns: 9876534210

  116. 234

    10

    Returns: 9876523410

  117. 418

    10

    Returns: 9874501362

  118. 528

    10

    Returns: 9876403152

  119. 1906

    10

    Returns: 9873156240

  120. 1130

    10

    Returns: 9876453120

  121. 4141

    10

    Returns: 9842705631

  122. 2476

    10

    Returns: 9861405372

  123. 8617

    10

    Returns: 9870325416

  124. 12032

    10

    Returns: 9852367104

  125. 26102

    10

    Returns: 9834607152

  126. 43461

    10

    Returns: 9860214375

  127. 134854

    10

    Returns: 8914523670

  128. 109325

    10

    Returns: 9468310275

  129. 443645

    10

    Returns: 8061473295

  130. 460329

    10

    Returns: 9265041783

  131. 1061673

    10

    Returns: 7615380429

  132. 735071

    10

    Returns: 6807492531

  133. 4315622

    10

    Returns: 207149856

  134. 2546252

    10

    Returns: 4972830156

  135. 10400969

    10

    Returns: 0

  136. 8449695

    10

    Returns: 6430217895

  137. 30154058

    10

    Returns: -1

  138. 39319410

    10

    Returns: -1

  139. 57830226

    10

    Returns: -1

  140. 98969914

    10

    Returns: -1

  141. 291451049

    10

    Returns: -1

  142. 223911036

    10

    Returns: 0

  143. 1112040101

    10

    Returns: -1

  144. 694852439

    10

    Returns: -1

  145. 2188685446

    10

    Returns: -1

  146. 2285780608

    10

    Returns: -1

  147. 5

    11

    Returns: 282458553895

  148. 7

    11

    Returns: 282458552355

  149. 10

    11

    Returns: 25678034240

  150. 24

    11

    Returns: 25678047432

  151. 46

    11

    Returns: 25678046262

  152. 63

    11

    Returns: 282458522115

  153. 182

    11

    Returns: 25678006172

  154. 147

    11

    Returns: 282458522115

  155. 726

    11

    Returns: -1

  156. 616

    11

    Returns: 25678033304

  157. 1792

    11

    Returns: 25677042944

  158. 1181

    11

    Returns: 282451296325

  159. 3120

    11

    Returns: 25675924560

  160. 3883

    11

    Returns: 282431616445

  161. 12784

    11

    Returns: 25670668304

  162. 14513

    11

    Returns: 282027573315

  163. 36272

    11

    Returns: 25620582112

  164. 56254

    11

    Returns: 25650023872

  165. 78605

    11

    Returns: 282432245485

  166. 117230

    11

    Returns: 25666805120

  167. 185111

    11

    Returns: 281691738695

  168. 266430

    11

    Returns: 25599660120

  169. 705034

    11

    Returns: 25601899642

  170. 687898

    11

    Returns: 25439843836

  171. 2708958

    11

    Returns: 25244779602

  172. 3738597

    11

    Returns: 230204110275

  173. 13957833

    11

    Returns: 44176541445

  174. 12777482

    11

    Returns: 14604661926

  175. 40599744

    11

    Returns: -1

  176. 41255221

    11

    Returns: 65802077495

  177. 101513697

    11

    Returns: 0

  178. 92113851

    11

    Returns: 0

  179. 375692739

    11

    Returns: -1

  180. 332930627

    11

    Returns: -1

  181. 423049007

    11

    Returns: -1

  182. 1040030615

    11

    Returns: -1

  183. 2300485502

    11

    Returns: -1

  184. 3382615371

    11

    Returns: -1

  185. 7393034162

    11

    Returns: -1

  186. 7574609718

    11

    Returns: -1

  187. 14023154974

    11

    Returns: -1

  188. 17233176487

    11

    Returns: -1

  189. 53763700681

    11

    Returns: -1

  190. 82348642865

    11

    Returns: -1

  191. 142178161820

    11

    Returns: -1

  192. 129356226082

    11

    Returns: -1

  193. 3

    12

    Returns: 8842413667560

  194. 4

    12

    Returns: 8842413667560

  195. 20

    12

    Returns: 8842413664260

  196. 25

    12

    Returns: 8842413643250

  197. 52

    12

    Returns: 8842413641776

  198. 33

    12

    Returns: 8842413667560

  199. 149

    12

    Returns: 8842412383695

  200. 194

    12

    Returns: 8842412861172

  201. 243

    12

    Returns: 8842412675547

  202. 577

    12

    Returns: 8842410911521

  203. 979

    12

    Returns: 8842413373695

  204. 1577

    12

    Returns: 8842367910288

  205. 2737

    12

    Returns: 8842395732786

  206. 5211

    12

    Returns: 8842302150264

  207. 6900

    12

    Returns: 8842412693400

  208. 10890

    12

    Returns: 8842406987700

  209. 22416

    12

    Returns: 8841484755312

  210. 28886

    12

    Returns: 8842395023176

  211. 82796

    12

    Returns: 8841723984940

  212. 155930

    12

    Returns: 8829688437680

  213. 445403

    12

    Returns: 8838758411021

  214. 434563

    12

    Returns: 8839356028459

  215. 953279

    12

    Returns: 8832457862976

  216. 1568891

    12

    Returns: 8770914944429

  217. 3810068

    12

    Returns: 8794677092564

  218. 3496821

    12

    Returns: 8813877203340

  219. 14238700

    12

    Returns: 8638847109200

  220. 14301304

    12

    Returns: 8757374901792

  221. 14684026

    12

    Returns: 8179266794468

  222. 37670413

    12

    Returns: 8819698454864

  223. 52958084

    12

    Returns: 7016681339580

  224. 66551234

    12

    Returns: 3708634065884

  225. 353491249

    12

    Returns: 6528629877781

  226. 169557740

    12

    Returns: 8753418327500

  227. 970939350

    12

    Returns: 2200148567100

  228. 750713103

    12

    Returns: 21770679987

  229. 1362775149

    12

    Returns: -1

  230. 2169436721

    12

    Returns: -1

  231. 6545844607

    12

    Returns: -1

  232. 5113413693

    12

    Returns: -1

  233. 10555761677

    12

    Returns: -1

  234. 11760561381

    12

    Returns: -1

  235. 69517146610

    12

    Returns: -1

  236. 45587374864

    12

    Returns: -1

  237. 243324642096

    12

    Returns: -1

  238. 245116453805

    12

    Returns: -1

  239. 370780598792

    12

    Returns: -1

  240. 821718339309

    12

    Returns: -1

  241. 2068531274342

    12

    Returns: -1

  242. 1754018891728

    12

    Returns: -1

  243. 5653215925698

    12

    Returns: -1

  244. 5208639404102

    12

    Returns: -1

  245. 2

    2

    Returns: 0

  246. 1

    2

    Returns: 1

  247. 1

    2

    Returns: 1

  248. 1

    2

    Returns: 1

  249. 8

    2

    Returns: -1

  250. 21

    3

    Returns: 0

  251. 15

    3

    Returns: 0

  252. 1

    3

    Returns: 19

  253. 14

    3

    Returns: -1

  254. 27

    3

    Returns: -1

  255. 134

    4

    Returns: -1

  256. 196

    4

    Returns: -1

  257. 17

    4

    Returns: -1

  258. 201

    4

    Returns: 0

  259. 32

    4

    Returns: -1

  260. 2887

    5

    Returns: -1

  261. 2008

    5

    Returns: -1

  262. 2058

    5

    Returns: -1

  263. 468

    5

    Returns: -1

  264. 25

    5

    Returns: -1

  265. 23082

    6

    Returns: -1

  266. 21700

    6

    Returns: -1

  267. 10940

    6

    Returns: -1

  268. 30315

    6

    Returns: -1

  269. 36

    6

    Returns: -1

  270. 616273

    7

    Returns: -1

  271. 102956

    7

    Returns: -1

  272. 703528

    7

    Returns: -1

  273. 481790

    7

    Returns: -1

  274. 98

    7

    Returns: -1

  275. 16395408

    8

    Returns: -1

  276. 4643714

    8

    Returns: -1

  277. 10704399

    8

    Returns: -1

  278. 9142249

    8

    Returns: -1

  279. 192

    8

    Returns: -1

  280. 152

    11

    Returns: 25678034120

  281. 101088

    12

    Returns: -1

  282. 100

    10

    Returns: -1

  283. 10000

    12

    Returns: 8842270800000

  284. 10000

    11

    Returns: 25675580000

  285. 144

    12

    Returns: -1

  286. 20016

    12

    Returns: -1

  287. 248832

    12

    Returns: -1

  288. 1000000000

    12

    Returns: -1

  289. 12347

    11

    Returns: 282412128445

  290. 407779

    9

    Returns: 3670011

  291. 4

    11

    Returns: 25678050212

  292. 1008

    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: