Statistics

Problem Statement for "ColorfulStrings"

Problem Statement

The product value of a string is the product of all the digits ('0'-'9') in the string. For example, the product value of "123" is 1 * 2 * 3 = 6.
A string is called colorful if it contains only digits and the product value of each of its nonempty contiguous substrings is distinct.

For example, the string "263" has six substrings: "2", "6", "3", "26", "63" and "263". The product values of these substrings are: 2, 6, 3, 2 * 6 = 12, 6 * 3 = 18 and 2 * 6 * 3 = 36, respectively. Since all six product values are distinct, "263" is colorful.
On the other hand, "236" is not colorful because two of its substrings, "6" and "23", have the same product value (6 = 2 * 3).

Return the k-th (1-based) lexicographically smallest colorful string of length n. If there are less than k colorful strings of length n, return an empty String instead.

Definition

Class:
ColorfulStrings
Method:
getKth
Parameters:
int, int
Returns:
String
Method signature:
String getKth(int n, int k)
(be sure your method is public)

Notes

  • The lexicographically smaller of two strings is the one that has the smaller character ('0' < '1' < ... < '9') at the first position where they differ.

Constraints

  • n will be between 1 and 50, inclusive.
  • k will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 3

    4

    Returns: "238"

    The first four smallest colorful strings of length 3 are "234", "235", "237" and "238".

  2. 4

    2000

    Returns: ""

    The number of colorful strings of length 4 is less than 2000.

  3. 5

    1

    Returns: "23457"

  4. 2

    22

    Returns: "52"

  5. 6

    464

    Returns: "257936"

  6. 1

    1

    Returns: "0"

  7. 1

    3

    Returns: "2"

  8. 1

    4

    Returns: "3"

  9. 1

    5

    Returns: "4"

  10. 1

    6

    Returns: "5"

  11. 1

    8

    Returns: "7"

  12. 1

    10

    Returns: "9"

  13. 1

    11

    Returns: ""

  14. 1

    430818442

    Returns: ""

  15. 1

    1000000000

    Returns: ""

  16. 2

    1

    Returns: "23"

  17. 2

    19

    Returns: "47"

  18. 2

    28

    Returns: "59"

  19. 2

    39

    Returns: "75"

  20. 2

    41

    Returns: "78"

  21. 2

    42

    Returns: "79"

  22. 2

    45

    Returns: "84"

  23. 2

    50

    Returns: "92"

  24. 2

    56

    Returns: "98"

  25. 2

    57

    Returns: ""

  26. 2

    624459040

    Returns: ""

  27. 3

    1

    Returns: "234"

  28. 3

    37

    Returns: "295"

  29. 3

    94

    Returns: "453"

  30. 3

    191

    Returns: "678"

  31. 3

    197

    Returns: "687"

  32. 3

    202

    Returns: "695"

  33. 3

    302

    Returns: "946"

  34. 3

    303

    Returns: "947"

  35. 3

    328

    Returns: "987"

  36. 3

    329

    Returns: ""

  37. 3

    635838948

    Returns: ""

  38. 4

    1

    Returns: "2345"

  39. 4

    607

    Returns: "5362"

  40. 4

    938

    Returns: "6948"

  41. 4

    1073

    Returns: "7629"

  42. 4

    1251

    Returns: "8576"

  43. 4

    1372

    Returns: "9345"

  44. 4

    1389

    Returns: "9376"

  45. 4

    1478

    Returns: "9682"

  46. 4

    1540

    Returns: "9876"

  47. 4

    1541

    Returns: ""

  48. 4

    387574968

    Returns: ""

  49. 5

    681

    Returns: "29873"

  50. 5

    1234

    Returns: "38794"

  51. 5

    1602

    Returns: "45862"

  52. 5

    1821

    Returns: "47928"

  53. 5

    3273

    Returns: "68472"

  54. 5

    3865

    Returns: "76349"

  55. 5

    5444

    Returns: "98362"

  56. 5

    5514

    Returns: "98765"

  57. 5

    5515

    Returns: ""

  58. 5

    449453393

    Returns: ""

  59. 6

    1

    Returns: "234578"

  60. 6

    541

    Returns: "259378"

  61. 6

    1130

    Returns: "278596"

  62. 6

    4797

    Returns: "479635"

  63. 6

    8072

    Returns: "659873"

  64. 6

    10206

    Returns: "785346"

  65. 6

    12337

    Returns: "927486"

  66. 6

    12733

    Returns: "943782"

  67. 6

    13956

    Returns: "987654"

  68. 6

    13957

    Returns: ""

  69. 6

    957095281

    Returns: ""

  70. 7

    1

    Returns: "2345789"

  71. 7

    3416

    Returns: "3469728"

  72. 7

    4324

    Returns: "3647958"

  73. 7

    6683

    Returns: "4528673"

  74. 7

    10799

    Returns: "5769283"

  75. 7

    14773

    Returns: "7384529"

  76. 7

    15287

    Returns: "7498356"

  77. 7

    16225

    Returns: "7894325"

  78. 7

    21596

    Returns: "9876543"

  79. 7

    21597

    Returns: ""

  80. 7

    451435243

    Returns: ""

  81. 8

    1

    Returns: "25346879"

  82. 8

    875

    Returns: "26893745"

  83. 8

    4659

    Returns: "39648725"

  84. 8

    10578

    Returns: "73964582"

  85. 8

    10698

    Returns: "74652893"

  86. 8

    10897

    Returns: "75693482"

  87. 8

    11643

    Returns: "82934657"

  88. 8

    12873

    Returns: "92685374"

  89. 8

    14256

    Returns: "98746253"

  90. 8

    14257

    Returns: ""

  91. 8

    818676059

    Returns: ""

  92. 9

    1

    Returns: ""

  93. 16

    7821

    Returns: ""

  94. 31

    3323

    Returns: ""

  95. 35

    3637

    Returns: ""

  96. 38

    975045199

    Returns: ""

  97. 39

    240352029

    Returns: ""

  98. 46

    525154836

    Returns: ""

  99. 50

    1

    Returns: ""

  100. 50

    1000000000

    Returns: ""

  101. 1

    2

    Returns: "1"

  102. 8

    666

    Returns: "26498573"

  103. 4

    4

    Returns: "2349"

  104. 47

    98734

    Returns: ""

  105. 13

    13

    Returns: ""

  106. 8

    11256

    Returns: "79362845"

  107. 9

    100

    Returns: ""

  108. 8

    555555

    Returns: ""

  109. 7

    20000

    Returns: "9468573"

  110. 6

    465

    Returns: "257938"

  111. 7

    1000

    Returns: "2648759"

  112. 8

    100

    Returns: "25398764"

  113. 8

    2

    Returns: "25346978"

  114. 7

    1000009

    Returns: ""

  115. 1

    10000

    Returns: ""

  116. 9

    65467

    Returns: ""

  117. 7

    1000000

    Returns: ""

  118. 8

    14000

    Returns: "97286345"

  119. 1

    14444

    Returns: ""

  120. 8

    10000

    Returns: "69582743"

  121. 17

    10007

    Returns: ""

  122. 7

    5000

    Returns: "3769584"

  123. 50

    1000

    Returns: ""

  124. 5

    765

    Returns: "34598"

  125. 50

    99990000

    Returns: ""

  126. 9

    200000

    Returns: ""

  127. 12

    14455

    Returns: ""

  128. 1

    1000

    Returns: ""

  129. 8

    12151

    Returns: "85273694"

  130. 8

    12

    Returns: "25348796"

  131. 8

    200

    Returns: "25498736"

  132. 8

    999999

    Returns: ""

  133. 9

    1000000

    Returns: ""

  134. 8

    1000

    Returns: "27359864"

  135. 8

    8

    Returns: "25347986"

  136. 8

    101

    Returns: "25436879"

  137. 8

    10464

    Returns: "73598264"

  138. 1

    103

    Returns: ""

  139. 49

    99999999

    Returns: ""

  140. 1

    100

    Returns: ""

  141. 8

    1000000000

    Returns: ""

  142. 7

    10

    Returns: "2347895"

  143. 9

    10

    Returns: ""

  144. 50

    5

    Returns: ""

  145. 8

    112

    Returns: "25438796"

  146. 8

    10

    Returns: "25348697"

  147. 8

    3

    Returns: "25347689"

  148. 8

    50000000

    Returns: ""

  149. 8

    12154

    Returns: "85274369"

  150. 50

    10000000

    Returns: ""

  151. 49

    1000000000

    Returns: ""

  152. 1

    20

    Returns: ""

  153. 8

    4999

    Returns: "43789256"

  154. 1

    12

    Returns: ""

  155. 1

    9

    Returns: "8"

  156. 7

    21595

    Returns: "9876534"

  157. 50

    10000

    Returns: ""

  158. 8

    1000000

    Returns: ""

  159. 8

    100000000

    Returns: ""

  160. 10

    1000000000

    Returns: ""

  161. 6

    753000

    Returns: ""

  162. 8

    500

    Returns: "25943876"

  163. 8

    12115

    Returns: "84953726"

  164. 9

    2000

    Returns: ""

  165. 8

    15200

    Returns: ""

  166. 8

    12345

    Returns: "86397254"

  167. 8

    12000

    Returns: "84652793"

  168. 8

    123

    Returns: "25467893"

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: