Statistics

Problem Statement for "CombinationLockDiv2"

Problem Statement

Andrew has a combination lock. The lock consists of multiple dials that are placed next to each other. Each dial contains the digits 0 through 9, in order. At any moment, exactly one of the digits on each dial is visible. The string formed by the currently visible digits is called the current combination.


The visible digit on a dial can be changed by rotating the dial up or down. Rotating the dial up changes 0 to 1, 1 to 2, and so on. Note that the digits on a dial wrap around: if we rotate up a dial that shows a 9, it will show a 0 again. Naturally, rotating the dial down changes the digit in the other direction.


We are able to rotate multiple dials at the same time, as long as they are next to each other. More precisely, in a single turn we can take an arbitrarily long segment of consecutive dials, and rotate all of them one step in the same direction (i.e., either all of them up, or all of them down).


For example, suppose that the current combination is "123". In one step, we can change it to many different combinations, including "012" (all three dials down), "234" (all three dials up), "133" (middle dial up), and "013" (first two dials down). Note that we cannot change "123" to "224" in a single step.


You are given two Strings: S and T. S is the current combination, T is the secret combination that unlocks the lock. That is, to open the lock we need to change S into T by rotating some of the dials. Return the smallest number of steps needed.

Definition

Class:
CombinationLockDiv2
Method:
minimumMoves
Parameters:
String, String
Returns:
int
Method signature:
int minimumMoves(String S, String T)
(be sure your method is public)

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • S will contain the same number of characters as T.
  • Each character in S and T will be a digit ('0'-'9').

Examples

  1. "123"

    "112"

    Returns: 1

    Rotate the last two dials down.

  2. "1"

    "7"

    Returns: 4

    Rotate the dial down 4 times: from 1 to 0, from 0 to 9, from 9 to 8, and from 8 to 7.

  3. "607"

    "607"

    Returns: 0

  4. "1234"

    "4567"

    Returns: 3

  5. "020"

    "909"

    Returns: 2

  6. "4423232218340"

    "6290421476245"

    Returns: 18

  7. "0183785"

    "0000000"

    Returns: 11

  8. "33333222322233333"

    "00000000000000000"

    Returns: 5

  9. "0123456789876543210"

    "0000000000000000000"

    Returns: 9

  10. "1234567890987654321"

    "0000000000000000000"

    Returns: 10

  11. "3789656"

    "5159478"

    Returns: 10

  12. "9277824328"

    "5457494629"

    Returns: 16

  13. "351832397"

    "783933521"

    Returns: 8

  14. "355070204"

    "676060327"

    Returns: 7

  15. "7426453582937390990599"

    "5243281321698807518024"

    Returns: 36

  16. "176734746409328221083"

    "164499178500552788873"

    Returns: 10

  17. "574149036467923059067"

    "340682246346935394635"

    Returns: 12

  18. "605671109043778650486220152344964"

    "052157799605842052820321751543033"

    Returns: 36

  19. "996315769104193210743926563394033848332"

    "873969080192858642844150020184156294011"

    Returns: 20

  20. "690221017521430132366153071208355064400"

    "466764227408084453356276427987367309078"

    Returns: 21

  21. "22109241798036080249208643709135880975390863"

    "80152752534914222910829807569979861784561356"

    Returns: 64

  22. "91764076679014302854836840311218635202200369261782"

    "10590882164643449864431120142394117791098627375510"

    Returns: 70

  23. "3893718543803167289010912803640497820625097763959"

    "7114706208235266055553122926096176832960665664183"

    Returns: 28

  24. "4199201645518106482753617475793802816510517321777"

    "6298077188728083036074605376927369606633963000789"

    Returns: 26

  25. "42323221834062904"

    "21476245378965651"

    Returns: 21

  26. "94789277824328545749462"

    "97839335216760603277426"

    Returns: 34

  27. "453582937390990599524328132169880751802416449917"

    "850055278887334068224634693539463560567110904377"

    Returns: 58

  28. "650486220152344964052157799605842052"

    "820321751543033873969080192858642844"

    Returns: 41

  29. "500201"

    "841562"

    Returns: 9

  30. "4011466764227408084453356276427987367309"

    "0782210924179803608024920864370913588097"

    Returns: 52

  31. "5390863801527525349142229108298075699798617845613"

    "5691764076679014302854836840311218635202200369261"

    Returns: 61

  32. "82105908821646434498644311201423"

    "94117791098627375510711470620823"

    Returns: 38

  33. "26605555312292609617683"

    "29606656641836298077188"

    Returns: 28

  34. "72808303607460537692736960663396300078966827177"

    "97188800723106837706034782220291427370931711916"

    Returns: 62

  35. "2390069375279223989186826963447017"

    "7324073849890926537064120570111519"

    Returns: 45

  36. "2979790780958516619352192169474637319864014737006"

    "8179431995047028504606260522563487301520334596840"

    Returns: 63

  37. "3"

    "4"

    Returns: 1

  38. "83216"

    "67458"

    Returns: 8

  39. "16436173113153215"

    "63398511567666159"

    Returns: 24

  40. "16903571944946235956386790292932226"

    "82446781821590556968621368193166783"

    Returns: 20

  41. "25934843597600221049999827170062208"

    "91477053474254542051234495071296765"

    Returns: 20

  42. "44980990286683930856871328173960974"

    "10423100163237251868116996074194431"

    Returns: 20

  43. "030493936306021114157883801666813551900"

    "917047257394786546258017368456936907689"

    Returns: 20

  44. "112095956"

    "544196180"

    Returns: 8

  45. "123456789"

    "000000000"

    Returns: 9

  46. "01234567890123456789"

    "00000000000000000000"

    Returns: 18

  47. "132"

    "000"

    Returns: 3

  48. "555555546555"

    "000000000000"

    Returns: 7

  49. "1233321"

    "0000000"

    Returns: 3

  50. "91919191"

    "00000000"

    Returns: 8

  51. "919191919"

    "000000000"

    Returns: 9

  52. "1213141516171819"

    "0000000000000000"

    Returns: 24

  53. "12123234345456567678789890901012123234345456567678"

    "00000000000000000000000000000000000000000000000000"

    Returns: 33

  54. "121232343454565676787898909010"

    "000000000000000000000000000000"

    Returns: 19

  55. "01234567890123456789012345678901234567890123456789"

    "00000000000000000000000000000000000000000000000000"

    Returns: 45

  56. "07418529630741852963074185296307418529630741852963"

    "00000000000000000000000000000000000000000000000000"

    Returns: 105

  57. "00236123469719800"

    "00000000000000000"

    Returns: 16

  58. "1"

    "0"

    Returns: 1

  59. "9"

    "0"

    Returns: 1

  60. "00000000000000000000000000000000000000000000000000"

    "50505050505050505050505050505050505050505050505050"

    Returns: 125

    about max answer

  61. "12347987984732789432009090909090904218989432814923"

    "21447812739923746784821749837498209099098423788737"

    Returns: 63

  62. "12345678901234567890123456789012345678901234567890"

    "22222222222222222222222222222222222222222222222222"

    Returns: 45

  63. "44232322184423232218442323221844232322184423232218"

    "90421476245629042147624562904214762456290421476245"

    Returns: 68

  64. "11111111"

    "33344444"

    Returns: 3

  65. "01234567890123456789012345678901234567890123456789"

    "01234567896290420123456789147012345678962012345645"

    Returns: 24

  66. "3094850397852098742039840329840239840329840329840"

    "2093802398403274983247320987402398402759328649328"

    Returns: 57

  67. "1234567891234567891234567891234567891234567897648"

    "5476541654324532416543213245215446564554324132416"

    Returns: 54

  68. "045515484151269715154154697784178841520215461"

    "788415202154610215454113645548704551548415124"

    Returns: 52

  69. "123"

    "135"

    Returns: 2

  70. "61245315859136861998168131400331549386718533622839"

    "34852109789707835297031580091362740674655155564356"

    Returns: 67

  71. "90834571634876398763898762123214789098764859860987"

    "09847564987456321456098374623432345687654758909874"

    Returns: 46

  72. "36753562912709360626187920237592289736129319478450"

    "00000000000000000000000000000000000000000000000000"

    Returns: 69

  73. "0550"

    "5005"

    Returns: 5

  74. "119088"

    "880911"

    Returns: 8

  75. "11223344556677889"

    "99323253555786869"

    Returns: 11

  76. "11111"

    "23232"

    Returns: 3

  77. "87895715891234567890123456789087219851691234567890"

    "49386571094961830527496183052784759817584961830527"

    Returns: 85

  78. "87589123761512387652875891237615123876528758912376"

    "42167128923471982741892374918278149471231212321348"

    Returns: 67

  79. "123456789"

    "987654321"

    Returns: 16

  80. "12221212156546121336664666464566465400000001115511"

    "11221313465464640012215454100008448779451512121212"

    Returns: 50

  81. "590"

    "681"

    Returns: 3

  82. "5555559555555"

    "0000007000000"

    Returns: 8

  83. "472547254725472547254725472547254725472547254725"

    "000000000000000000000000000000000000000000000000"

    Returns: 76

  84. "0168511300"

    "0947977456"

    Returns: 12

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: