Statistics

Problem Statement for "LeftRightDigitsGame2"

Problem Statement

You are playing a solitaire game called Left-Right Digits Game. This game uses a deck of N cards. Each card has a single digit written on it. These digits are given as characters in the String digits. More precisely, the i-th character of digits is the digit written on the i-th card from the top of the deck (both indices are 0-based).

The game is played as follows. First, you place the topmost card (whose digit is the 0-th character of digits) on the table. Then, you pick the cards one-by-one from the top of the deck. For each card, you have to place it either to the left or to the right of all cards that are already on the table.

After all of the cards have been placed on the table, they now form an N-digit number. You are given a String lowerBound that represents an N-digit number. The primary goal of the game is to arrange the cards in such a way that the number X shown on the cards will be greater than or equal to lowerBound. If there are multiple ways to satisfy the primary goal, you want to make the number X as small as possible.

Return the smallest possible value of X you can achieve, as a String containing N digits. If it is impossible to achieve a number which is greater than or equal to lowerBound, return an empty String instead.

Definition

Class:
LeftRightDigitsGame2
Method:
minNumber
Parameters:
String, String
Returns:
String
Method signature:
String minNumber(String digits, String lowerBound)
(be sure your method is public)

Notes

  • lowerBound has no leading zeros. This means that any valid number X should also have no leading zeros (since otherwise it will be smaller than lowerBound).

Constraints

  • digits will contain between 1 and 50 characters, inclusive.
  • Each character of digits will be between '0' and '9', inclusive.
  • lowerBound will contain the same number of characters as digits.
  • Each character of lowerBound will be between '0' and '9', inclusive.
  • The first character of lowerBound will not be '0'.

Examples

  1. "565"

    "556"

    Returns: "556"

    You can achieve exactly 556. The solution is as follows: Place the first card on the table. Place the second card to the right of all cards on the table. Place the last card to the left of all cards on the table.

  2. "565"

    "566"

    Returns: "655"

  3. "565"

    "656"

    Returns: ""

    The largest number you can achieve is 655, but it is still less than 656.

  4. "9876543210"

    "5565565565"

    Returns: "5678943210"

  5. "8016352"

    "1000000"

    Returns: "1086352"

  6. "0"

    "1"

    Returns: ""

  7. "5"

    "5"

    Returns: "5"

  8. "5"

    "4"

    Returns: "5"

  9. "4"

    "5"

    Returns: ""

  10. "00000000000000000000000000000000000000000000000000"

    "10000000000000000000000000000000000000000000000000"

    Returns: ""

  11. "00000000000000000000000000000000000000000000000009"

    "77777777777777777777777777777777777777777777777777"

    Returns: "90000000000000000000000000000000000000000000000000"

  12. "00000000000000000000000000000000000000000000000009"

    "99999999999999999999999999999999999999999999999999"

    Returns: ""

  13. "3"

    "1"

    Returns: "3"

  14. "08"

    "89"

    Returns: ""

  15. "068"

    "356"

    Returns: "608"

  16. "0067"

    "4008"

    Returns: "6007"

  17. "35410"

    "25545"

    Returns: "35410"

  18. "310938"

    "847579"

    Returns: "890133"

  19. "0916929"

    "2151053"

    Returns: "2190699"

  20. "07078383"

    "48812165"

    Returns: "70078383"

  21. "235994996"

    "373020932"

    Returns: "423599996"

  22. "8917532537"

    "9447538653"

    Returns: "9817532537"

  23. "36403829258"

    "83994503502"

    Returns: "84360329258"

  24. "370035289599"

    "251490009789"

    Returns: "253003789599"

  25. "4695057679329"

    "2124485185683"

    Returns: "2304695576799"

  26. "45527201837242"

    "92788746069371"

    Returns: ""

  27. "881324356505788"

    "781132987291731"

    Returns: "788132435650588"

  28. "8724483375744806"

    "7433078356500676"

    Returns: "7442788335744806"

  29. "38970557828774226"

    "95480025359174697"

    Returns: "98370557828774226"

  30. "725431577753493721"

    "892333704165426715"

    Returns: "912754357775343721"

  31. "2755894113062675191"

    "2195549924694362705"

    Returns: "2195572841306675191"

  32. "54880697764616510142"

    "56781948547726329061"

    Returns: "56784580697461610142"

  33. "522042136022636254641"

    "559737750935742501186"

    Returns: "560022542136223624641"

  34. "6546702755696041797967"

    "3311557917772180683713"

    Returns: "4004566727556961797967"

  35. "65020785252093803529006"

    "92935012660549842608015"

    Returns: "92950056278252038035006"

  36. "738084858857841946011822"

    "454621627181030803005183"

    Returns: "454738088588781946011822"

  37. "9161360312188956223616528"

    "2710273188091634750631433"

    Returns: "2801196363121895622361658"

  38. "71902829060153852898546968"

    "95003383463283393317509125"

    Returns: "95007190282961385288546968"

  39. "065719945873917058283256381"

    "111410031089810180985956027"

    Returns: "111506799458739705828325638"

  40. "8535318031205747726058531884"

    "1496211430806307166034108805"

    Returns: "1500013358583125747726583884"

  41. "71776668268500781552364414434"

    "92680018933371862476321796100"

    Returns: ""

  42. "829775674302975703295235550654"

    "475770040807624506549440935519"

    Returns: "475772895674302970329523555065"

  43. "3379400061403038652000567469739"

    "4061703815708007555116280004087"

    Returns: "4061733940006403038520056769739"

  44. "64685390727936112473876667344950"

    "79109029525737109689800614212694"

    Returns: "79203466859773611243876667344950"

  45. "721858832037465252878884140892524"

    "312664024719560340782742991335372"

    Returns: "312785882037465252878884140892524"

  46. "7122137850439491896196849625015157"

    "4235777194286161215177324957003468"

    Returns: "4271213785039491896196849625015157"

  47. "72807840675529932723935303389993712"

    "74129620363236558150880780703137207"

    Returns: "74278078065529932723935303389993712"

  48. "305988166842031992596942811828787505"

    "663450544274918830985230286853611965"

    Returns: "665039881684203199259942811828787505"

  49. "1400655009179254568215851827762040228"

    "2958085246288254831504923505285542244"

    Returns: "2960014550017925456815851827762040228"

  50. "69926079855844265636078454482903513389"

    "91589358220348339033869961068500508110"

    Returns: "91589626990755844265636078444829035338"

  51. "633512720790947594025755073071831947914"

    "791888405689502396247749736743360032634"

    Returns: "791890013365272794759402575507307134914"

  52. "2014388552887885426468052500360035896213"

    "4591480711260210173724852233512705387936"

    Returns: "4602143885528878854268052500360035896213"

  53. "73567070347488136186801351881487179279375"

    "76983994759155482845476287984980241256264"

    Returns: "77000375677347488136186813518814817927935"

  54. "701991295537619538050804723930296143184164"

    "880665577171098563655869236735303745451295"

    Returns: "880670199129553719538050472393029614314164"

  55. "3596381462591125539826578084597570038182126"

    "2510595515312800017871815996191029783755083"

    Returns: "2511133596846259253982657808459757003818126"

  56. "15164277574703450538807263856289489054834154"

    "68637134529651527195210893473676771562410157"

    Returns: "68637151642757470345058807235289489054834154"

  57. "580324574874033623750758844156562781214263060"

    "403327943408329743014060301840277561040284242"

    Returns: "403328503457487403627575884156562781214263060"

  58. "9691052684329061793323289833024290320948107435"

    "6209841260552042755485797419183574836644895616"

    Returns: "6209961526843901793323289833024290320948107435"

  59. "15396453747588897025305574015633237095832465610"

    "73496847884108950897552249986700604414462181175"

    Returns: "73496915345374758887025305570156323095832465610"

  60. "531874936262806092431525927760768700019212938398"

    "897104778987341838792108336232745332274279280147"

    Returns: "897104781359362628069243525927607687000121293398"

  61. "9613963206361956826579275983537488795314240324017"

    "2286079350108094970403342259916655130449482506546"

    Returns: "2286091693632361956265792759835374887953144034017"

    2286091693632361956265792759835374887953144034017

  62. "82337747184963159887462482340704959847287618876913"

    "81729240748720231938344986638649960138494198455928"

    Returns: "81729241128337747849635988746283407045984786876913"

  63. "31675269682330430957542344996389950693403077228885"

    "11731956602838487388603622405369346965073676360312"

    Returns: "13675269682330430957542344996389950693403077228885"

  64. "24747310951154358777272966199021198272431912077219"

    "42033057611009499874689347457528175994232723271473"

    Returns: "42033247471095115458777272966199119827231912077219"

  65. "20404772512064863409850260654464156524175712431654"

    "43015849659357081774760578899157583305443615826636"

    Returns: "43017002447252064863409850266544641565241757124165"

  66. "75491280600948596024623532367855092605130078770302"

    "20597264768617372735078177268844724789450401068690"

    Returns: "20597264800014579286945960223533685502601300787703"

  67. "74329319488258988260539971321411116704058605445694"

    "18120043461391221814685668380718261899819509966746"

    Returns: "18123479394825898826053997132141116704058605445694"

  68. "40825892202622982578009162138742301673131182508036"

    "64770805273494818409754967019545705329853476922565"

    Returns: "64770820485922262298258009162138230167313118250803"

  69. "48971111684219806998240010987384431885797673670178"

    "13759089693307969481878920534911439689760379789225"

    Returns: "13759089694111148976821809240018738443188796767078"

  70. "18982063564753892085460897605745302113993732696377"

    "83106844408861728624730486424908801923812501881514"

    Returns: "83189820635647589205460897605745302113993732696377"

  71. "28730980356895006799728787223591010592420808780165"

    "31551233558510072995743688019055710947243222339120"

    Returns: "32000028739835689567997287872591010592420808780165"

  72. "12558336022492459945572656496089857074349555403601"

    "38352741655738737597098682805683045793340115960533"

    Returns: "38355128360224924599455726564960895707434955540601"

  73. "51679522928591115332427616337533252968971895540341"

    "83653673018269440269894186724620153595000906184214"

    Returns: "83655156792292859111332427163375325296897195540341"

  74. "34632592580364009800101794703389979890835468533261"

    "94622412551245134639485918400837500584796530697242"

    Returns: "94622436359580300800101794703389979890835468533261"

  75. "21326380011206248335115400465768225440827556731821"

    "66542249940878288990239943100710527042699788869844"

    Returns: "66542261232380011064833511500467822544082755731821"

  76. "01963628099683912387128159821807731934959286874355"

    "60938997723477527255908175853934059922182675540466"

    Returns: "60938998019636206123871281598218773193495928874355"

  77. "54787495663306382764908265325790227829634964053439"

    "56533053985310123218965348735554608785556850407792"

    Returns: "56533054457879663368276490826527902278293496403439"

  78. "99384987030503088257300735738751021522204194059522"

    "51182370705865794473842485242565307416681837828600"

    Returns: "51182373998498005030885730073573750215222049405922"

  79. "07034046961703820316696523713389466320294675670512"

    "83701131345018130146181335883436560589170764604221"

    Returns: "83701300740469670382316696523139466320294675670512"

  80. "61267014762850629728446449698259320898678803917065"

    "62582170120536496579109068800315333384694182478485"

    Returns: "62582171626047606297284464496982593089867880391705"

  81. "81631218361325452242732474929912737972710326613615"

    "99488726195008366641597069811810816234948325718715"

    Returns: "99511118632836324522427324742912737972710326613615"

  82. "03615336633252113759145894152856317009112341161939"

    "41696050336245953840846454398340263483708749417150"

    Returns: "41696103653363325211375145894152853170091231161939"

  83. "00011110101101101110001100011000100111101011011010"

    "10001010010000000101111101001110000101010111011001"

    Returns: "10001010010000000101111101100011001100111111111110"

  84. "11110010110011010110011110100111000101011110111110"

    "11000010010000100011000110001110011010100110010110"

    Returns: "11000010010000100011000111111111111111001111111110"

  85. "10001011010111000110001000110010001101111001100111"

    "10011011111110110111110001111000011110011111001101"

    Returns: "10011011111110110111110010000110000000000000111011"

  86. "01111101110100110000000000011110011010001000110001"

    "10110101110111111010010011101011111000110111010101"

    Returns: "10110101110111111010010111111100000000000000000000"

  87. "11111100001101010111100110101110010111110110001100"

    "11011100100010000100011000000001011010100100111111"

    Returns: "11011100100010000111111000111111101111101110001100"

  88. "11011001001111100000100111000101110001101101100011"

    "10011110001010101101011101000111100101111011111110"

    Returns: "10011110001010101101011101001110000001110011001101"

  89. "11001010101111000001100011000111010110010101001111"

    "10100110111011111011011110011010001010100011001101"

    Returns: "10100110111011111011100001000000010001110100110111"

  90. "00111001110000100010010110011000100000011101000110"

    "11110100101111010111101001111100000001100011010000"

    Returns: "11110100101111010111110000100000000010000000000110"

  91. "11001010001011010011010110010110101110111011000111"

    "10010000110011100001100101111110110001101111101100"

    Returns: "10010000110011100001100110000101111100111111111011"

  92. "01010111101001001100100011001000000010010110101010"

    "11001000001111101011101100010001100100100111010011"

    Returns: "11001000001111101011101100100000000100100000111100"

  93. "00010000000000000000000000000000000000000000000000"

    "10000000000000000000000000000000000000000000000000"

    Returns: "10000000000000000000000000000000000000000000000000"

  94. "00010000000000000000000000000000000000000000000000"

    "10000000000000000000000000000000000000000000000001"

    Returns: ""

  95. "44262487200663752766554168965678024449091021293154"

    "19079782244642006637527665541686568024449021293154"

    Returns: "19079782244642006637527665541686568024449021293154"

  96. "94467883211437775598162033100913234128068892301340"

    "47411234496788377559816203310091323128068892301340"

    Returns: "47411234496788377559816203310091323128068892301340"

  97. "87362893378460497518920615692204882128381365318586"

    "22158237868933746049718920656904882128381365318586"

    Returns: "22158237868933746049718920656904882128381365318586"

  98. "55360298345822405188969587960270241512477023448189"

    "95149519035562834582240588969876027021247702344818"

    Returns: "95149519035562834582240588969876027021247702344818"

  99. "47279613014107035955847160284520975073178863623741"

    "31671924776130140035955847102845209750737886362741"

    Returns: "31671924776130140035955847102845209750737886362741"

  100. "44003091376486771067003290056773819011628755020075"

    "95660004439137486771070032900677381011628755020075"

    Returns: "95660004439137486771070032900677381011628755020075"

  101. "03616805500073015466453092319401831741965349590549"

    "30000000036168557315466453923194181741965349590549"

    Returns: "30000000036168557315466453923194181741965349590549"

  102. "04690193454653920630909810861755014738444076468886"

    "31290046913454653906309098086175501478444076468886"

    Returns: "31290046913454653906309098086175501478444076468886"

  103. "13693704079108480628204167963864953930871299292463"

    "18287913630407910480620416796386495393087299292463"

    Returns: "18287913630407910480620416796386495393087299292463"

  104. "71618950635842309285901304619259605475707733630230"

    "88011768956354230925901304619259605475707733630230"

    Returns: "88011768956354230925901304619259605475707733630230"

  105. "28232219161041723277279976977283168400720121342808"

    "38160111222283964172327727997977283640072012142809"

    Returns: "38160111222823964172327727997977283640072012142808"

  106. "69011291205141246910405025321752546596652265199692"

    "11390069112912514124610405025275254659665226599693"

    Returns: "11390096112912514124610405025275254659665226599692"

  107. "23504384911696504525881887770940768401477561534206"

    "92180235434916965045588188777040768401477561534207"

    Returns: "92180325434916965045588188777040768401477561534206"

  108. "02187900548038306206087157675220555015177411034896"

    "81320187900548038062060871576752205550151774103497"

    Returns: "81320187900548038062060871576752205550157741103496"

  109. "85538361122488134995239235712605848687412593625504"

    "10241113355886224883995239235716584868742593625505"

    Returns: "10241113355886224883995239357126584868742593625504"

  110. "09276938648651301767548870072577269651471846102629"

    "24806509276938648613017754887072577269651471610270"

    Returns: "24806509276938648613017754887072577269651471610629"

  111. "21247701532424804005654286660147067044739084002361"

    "26847212470153224040055428666014706704473908400362"

    Returns: "26847212470153224040055486660147067044739084002361"

  112. "92089583423526979964922726079522935371162763489668"

    "56582908953423269799492272607922935371162763489669"

    Returns: "56582908953423269799492272607952293371162763489668"

  113. "08563069736134568134930267822031983976504244383750"

    "16073085606936134568134932782203983976504244383751"

    Returns: "16073508606936134568134932782203983976504244383750"

  114. "22283375788952998280235623996945902896551888023210"

    "15326202222283375788959988359969459028965188802321"

    Returns: "15326202222283375788959988359969459028965888023210"

    15326202222283375788959988359969459028965888023210

  115. "10001111110110110000110010111101101111110101000101"

    "10010100000000110111010011101100111111111111111001"

    Returns: "10010100000000110111010011101100111111111111111001"

  116. "10110101000011001100011000000111111000001101011001"

    "10111110001011110110011100101000000000001111100000"

    Returns: "10111110001011110110011100101000000000001111100000"

  117. "00010010001001111110010010111101110000100110001101"

    "11101001111010110110011100000000111100011100001000"

    Returns: "11101001111010110110011100000000111100011100001000"

  118. "01000110001110100001011000001111010100001001110001"

    "11001101011011001010001110000110001000011000010001"

    Returns: "11001101011011001010001110000110001000011000010001"

  119. "01110010111101101011111110011010101100101110011011"

    "10100010110000001101111011000110111111111111011111"

    Returns: "10100010110000001101111011000110111111111111011111"

  120. "01000111110011101001110100101001110001101000000011"

    "10010101111101110000101111100000001110001101000010"

    Returns: "10010101111101110000101111100000001110001110000001"

  121. "11100110010000100110100010001000111100000110011001"

    "10101001111011101011001100111000001000000000001011"

    Returns: "10101001111011101011001101110000001000000000001010"

  122. "00110011000110110101010111111110000000111100010000"

    "10000010101010110000000011111111111110000011110001"

    Returns: "10000010101010110000000011111111111110000111100000"

  123. "11110001000111100000100000000010010010010101000100"

    "10011100111110000001111000000000000000010010101001"

    Returns: "10011100111110000001111000000000000000010010110000"

  124. "10001011010010110110000101010110110001110111100111"

    "10101000010010111100111000010100100001111111111100"

    Returns: "10101000010010111100111000010100100010111111111011"

    10101000010010111100111000010100100010111111111011

  125. "24120361070998207884629926669915413549501374923069"

    "53326122285316127548532392553030408672164827164085"

    Returns: "53342120610709982078846299266699154149501374923069"

  126. "7828"

    "8664"

    Returns: "8728"

  127. "01010101010101010101010101010101010101010101010101"

    "10110101100011010110001101011000110101100011010100"

    Returns: "10110101100011010110001101011000110101100011010100"

  128. "56556556556556556556556655655655565566556556655655"

    "56656565565565565565565565565565565565565565565565"

    Returns: "56656565565565565565565565565565565565565565565565"

  129. "17409488245517115276142322168576189279543123341138"

    "64277931986502860248650900613893446066184963788291"

    Returns: "64278017494824551115761232216857189279543123341138"

  130. "29384756233984765387648494847464849487322174456"

    "59842948573920283857389309283849238482934958482"

    Returns: "59843229384756339847658764484746484948732217446"

  131. "01010101010101010100000001111111100011011011101001"

    "11110110000000101110001001011100111111001001110001"

    Returns: "11110110000000101110001001011100111111001001110001"

  132. "01234"

    "31024"

    Returns: "31024"

  133. "0182984729798237562327640756075756881883401231945"

    "3459837953498579348759834769379675993134994658947"

    Returns: "3459880129472798237562327640756075768818830121945"

  134. "56545753525859515258535754565553585957525051"

    "58545753525859515258535754565553585957525051"

    Returns: "58545753525865545753525591558565535595725051"

  135. "12345678901234567890123456789012345678901234567890"

    "11111111111111111111111111111111111111111111111111"

    Returns: "11111234567890234567890234567890234567890234567890"

  136. "13232323232323232323232323232323232323232323232324"

    "43333333333333333333333312222222222222222222222222"

    Returns: "43333333333333333333333312222222222222222222222232"

  137. "63220680150400754218533501245023126179391466089009"

    "62681500758350124523167910890836531281196090887463"

    Returns: "62700000223668154541853350124502312179391466089009"

  138. "12345678901234567890123456789012345678901234567890"

    "10000000000000000000000000000000000000000000000000"

    Returns: "10000123456789123456789123456789123456789234567890"

  139. "55555555555555555555555555555555555555555555555555"

    "44444444444444444444444444444444444444444444444444"

    Returns: "55555555555555555555555555555555555555555555555555"

  140. "99999999999999999999999999999999999998999999998999"

    "10000000000000000000000000000000000000000000000000"

    Returns: "88999999999999999999999999999999999999999999999999"

  141. "121212121212121212521232121212121212121212121212"

    "121212121212121212121212121212121212121212121212"

    Returns: "121212121212121212121212121212121212121212125232"

  142. "59045940393934509345905390395034590345930359555345"

    "12345678901234567890123456789012345678901234567890"

    Returns: "30000000059459439393459345953939534593459335955545"

  143. "5430319999"

    "3457137961"

    Returns: "3540319999"

  144. "598795421498745566345221452000326063030326565"

    "486132153013036846484300044306465406546500462"

    Returns: "487598954214974556634522152000326063030326565"

  145. "43574141794350265322231608993907688128285"

    "38601412159297218638710676408991409334836"

    Returns: "38601413457479435253222316099907688128285"

  146. "478"

    "633"

    Returns: "748"

  147. "1234567890"

    "1000000000"

    Returns: "1234567890"

  148. "9324857934875893478957348957348978934747384759385"

    "5328758934758934795834897432897598324748932784234"

    Returns: "5329348579348758934789573489573489789347473847598"

  149. "75"

    "66"

    Returns: "75"

  150. "14877705255934671197265232435804391933463030504927"

    "77516673942074559304004913242358337652171495383209"

    Returns: "77520148777559346119265232435804391933463030504927"

  151. "99999988888777777666666555555444444333333322222222"

    "11111111111111111111111111111111111111111111111111"

    Returns: "22222222333333344444455555566666677777788888999999"

  152. "555666777"

    "767676555"

    Returns: "775556667"

  153. "0626"

    "2929"

    Returns: "6026"

  154. "98409053152361505509949047124075204974148011539825"

    "35668709493130786707228549021927334644301060638287"

    Returns: "35689409053152310550994904712407520497414801159825"

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: