Statistics

Problem Statement for "SortMachine"

Problem Statement

We have a sorting machine that works on a list of distinct numbers. This machine only has one instruction named MOVE that takes one element of the list as a parameter. The MOVE instruction removes the element from the list and then appends it to the end of the remaining list.

For example, the sequence {19,7,8,25} can be sorted in ascending order using 2 instructions:
MOVE 19, to get {7,8,25,19}
MOVE 25, to get {7,8,19,25}

You will be given a int[] a containing a list of distinct numbers. Return the minimum number of instructions required to sort the list in ascending order.

Definition

Class:
SortMachine
Method:
countMoves
Parameters:
int[]
Returns:
int
Method signature:
int countMoves(int[] a)
(be sure your method is public)

Constraints

  • a will have between 1 and 50 elements, inclusive.
  • Each element of a will be between -1000 and 1000, inclusive.
  • All elements of a will be distinct.

Examples

  1. {19,7,8,25}

    Returns: 2

    The example from the problem statement.

  2. {1,2,3,4,5}

    Returns: 0

    This list is already sorted, so no instructions are needed.

  3. {1000,-1000,0}

    Returns: 1

    This list can be sorted with a single instruction: MOVE 1000.

  4. {2,1,3,4,5,6,7,8,9}

    Returns: 8

  5. {4,5,1,6,7,2,8,9,3,10,11}

    Returns: 8

  6. {1,3,4,5,6,7,8,9,2}

    Returns: 7

  7. {10,11,12,1,3,4,5,6,7,8,9,2}

    Returns: 10

  8. {-6, 5, 1, -8, 2}

    Returns: 4

  9. {-2, -8, 9, 0}

    Returns: 3

  10. {731, 87, 48, 660, 57, 784, -613, -680, -207, -454, 589, 67, 136}

    Returns: 12

  11. {988, 54, -2, 128, 353, 429, 638, 123, -369, 127, 334, -543, 465, -177, 892, 386}

    Returns: 15

  12. {377, -492, -739, -771, 313, 741, 382, -407, 105, 883, -352, 268}

    Returns: 11

  13. {269, 214, -460, -438, 488, 665, 854, 887, -255, -688, -766, -879, -518, 374, 17, -49, 642, -837, -555, 880, 267, 200, -117, -495, 635, -659, -37, -332, -945, -632, -968, -612, 18, 678, 146, -725, 866, -748, 276, -892, -970, 157, -215, -717, 260, -314}

    Returns: 45

  14. {106, 307, -682, -482, 877, -650, 705, 845, 787, -402, 988, -762, 795, 973, -409, -107, 623, -10, -300, -659, 644, 262, 878, 754, -279, 972, 18, -686, 703, 255, 341, -623, 163, -621, -987, 480, -632}

    Returns: 36

  15. {-39, -198, 649, 663, -443, 907, 81}

    Returns: 6

  16. {471, 252, -192, 888, 100, -727, -254, -870, 74, -904, 770, -650, 934, -180, 518, -892, -454, -721, -369, -612, -780, -832, 367, -643, 933, -50, -631, -315, 2, 800, 677, 853, -761, -875, 635, 964, 449, -281, -776, 960, 552, 472, -107, 28, 368}

    Returns: 42

  17. {268, 431, -291, 446, -94, -576, 318, 327, -131, 853, -733, 136, 108, -823, -994, -577, 440, -439, 605, 937, -34, 384, 778, 173, 791, -136, -781, -353, -867, 618, 874, 171, 864, -705}

    Returns: 32

  18. {-233, -87, 74, 416, -718, 468, -294, 712, -349, -752, -734, -69, 433, -939}

    Returns: 13

  19. {711, 739, -956, 917, -566, -152, 194, 222, 12, 405, -290, -728, -998, 306, 974, 768, 250, -841, -827, 586, -511, 495, -626, -817, 960, 627, -164, -264, 70, 752, -883, -300, -694, -851, -786, -638, 880, -779, -610, 459, -861}

    Returns: 40

  20. {-916, -470, 686, -399, 343, 372, 167, 703, 229, 216, -773, 610, 584, 368, 518, 91, 228, -313, -444, 690, 62, -147, 436, 570, 212, 700, 60, -720}

    Returns: 25

  21. {-771, 392, -52, 930, -51, -789, 94, 695, -37, -772, -956, 691, 559, 226, -940, -728}

    Returns: 14

  22. {460, 52, 149, 895, -217, 946, -41, 482, 260, -723, -153, 674, 892, 201, 565, 321, 619, 497, 159, 142, -743, 813, 860, 600, -554, -477, -63, 898, -868, -473}

    Returns: 29

  23. {-43, 528}

    Returns: 0

  24. {-889, -295, 581, -251, -195, -337}

    Returns: 4

  25. {195, 462, 545, 141, -225, 611, 454, 772, -714, 403, -641, -940, 436, -86, -401, -497, 211, -120, 964, 680, -466, -885, 894}

    Returns: 21

  26. {-628, 789, 508, 140, -762, 39, 192, 714, 869, 755, 950, -66}

    Returns: 11

  27. {-957, 531, -279, -179, 461, -482, -259, 249, 704, -530}

    Returns: 8

  28. {258, 137, -338, -591, -793, -404, 636, 424, 238, 85, -394, 707, 506, 919, -150, -175, -313, -51, -540, -787, -56, -234, 902, 951, -603, -141, 986, -783, -510, 276, -738, -906}

    Returns: 31

  29. {619, 98, -825, 184, 253, -168, -723, -640, 381, -866, -534, 998, 434, -182, 839, -34, -916, -515, -858, 316, -155, 285, -639}

    Returns: 22

  30. {292, -76, 379, 996, -655, 11, 780, 752, 56, 333, -566, -333, 471, -494, -668, -430, -760, -662, -577, 159, -600, -212, 598, 938, -1, 429, 817, 535, 485, 264, -810, -970, 814, -269, -364, 798}

    Returns: 35

  31. {157, 115, 400, 623, 234, -455, 421, -178, -378, -164, 906, 73, -624, -967, 742, 551, 995, 581, 397, -560, -151, 687, -476}

    Returns: 22

  32. {114, -205, -753, -852, -190, 611, 911, -195, -944, -895, 403, -603, -393, 86, -98, -628, -516, 679, 457, 945, -632, -185, -90, -976, 399, -1, -871, 176, -228, 279}

    Returns: 29

  33. {488, -796, 788, -607, -797, -227, 648, 279, -118, -425, 520, -935, 555, -480, -277, 6, -229, 980, 634, 139, -239, -390, 958, -414, -930, -994, 18, -553, -743, -783, -352, 823, -708, 828, 372, -851, 898, -580, -202, 263, 80}

    Returns: 40

  34. {710, 24, 650, 487, -7, -269, -884, -337, -111, -174, 170, 618, -559, 355, 377, 677, -756, -718, -945, 670, -893, -75, -866, 60, -757}

    Returns: 23

  35. {653, 368, -695, 727, 350, -480, -182, 956, 840, -618, 522, 435, -615, 14, -163, -946, 942, -121, 498, -502, 384, -265, 545, 822, -338, 92}

    Returns: 25

  36. {336, 596, 170, -971}

    Returns: 3

  37. {429, -990, -565, 873, 736, 898, -464, 355, -686, 104, 157, 263, -254, 972, 249, 546, 743, 990, -853, -732, 693, -716, 692, -166, 741, -468, 211, -353, -812, -306, 511, -975, -360, 697, 146, 32, 711}

    Returns: 35

  38. {483, -426, -6, -353, -337, 37, -453, 758, -258, 971, 161, -934, 502, -499, -134, -111, 456, 859, 732, -919, 578, -505, -36, 96, -498, -288, 940, -112, 881, 76, -444, 239, 661, -621, 990, -526, -583, 311, -469, -15, 489, -483, 448}

    Returns: 39

  39. {-394, -646, -989, 959, 620, 631, -254, -819, -922, 919, 302}

    Returns: 9

  40. {-827, 292, -3, -225, 982, 680, -126, -258, 447, -461, 8, 952, 454, -311, -848, -841, -217, 160, -24, 15, 255, 502, -907, 943, 907, 500, 914, 289, -533, 719, 302, -2, -634, -518, 934, -585, 562, -246, -531, 654, -915, -845, -275, -345, -365, 735, -975}

    Returns: 46

  41. {976, -946, -824, 680, -644, -95, 128, -892, 816, -263, -592, -669, 887, 447, -653, -759, 572, 171, 635, 98, -904, 78, 143, -416, -40, -846, 784, -702, -738, -858, 582, 603, -535, 529, 84, -964, 934, 36, 783}

    Returns: 38

  42. {44, 286, -49, -246, -378, 403, 511, 299, 18, 868, 938, 824, -403, 416, -697, -157, -652, -72, -132, 512, -290, 74, -707, -948, -812, 426, 806, 757, 118, 884, 292, -765, 363, 855, -460}

    Returns: 32

  43. {-875, 489, 452, 897, 199, -428, 809, 752, -395, -272, -618, 172, -483, 276, -380, -79, -602, -43, 679, 471, -960, 245, 605, 25, -771, 325, -98, -742, -20, 876, 640, -597, 908, -831, -836, -871, -54, -925, -939, -560, -662, 773, -393, -247, 202, 833}

    Returns: 44

  44. {307, -452, -97, -811, -831, -420, 669, -990, -64, 40, 840, -380, -206, -183, 282, -888, -748, -30, -121, 140, -717, 208, 631, 950, -248, 997, -407, -773, -267, 994, -896, -942, 504, 377, -331, -676, -552, 750}

    Returns: 36

  45. {295, 916, -419, 716, -139, 140, -735, 299, -625, 120, -596, -969, 259, -506, 956, -844, -937, 875, 607, 182, 448, -988, 793, -884, -82, 405, -318, -87, -90, -615, 260, -748, 224, 323, 868, 215, -467, 88, -331, -561}

    Returns: 39

  46. {-340, 659, 183, 935, 517, 902}

    Returns: 3

  47. {158, 497, -55, -581, 228, -193, 710, 704, -963, 750, 830, 466, -425, -15, 834, -478, -737, -754, -499, 231, 885, 344, -135, 424, -139, -646, -832}

    Returns: 25

  48. {318, -657, 375, -622, 959, -196, -207, 456, -506, -128, -888, 991, -350, -591, -895, -486, -847, 146, -414, -405, 874, 414, -158, 166, 478, 269, 599, -238, 334, 383, -360, -464, -41, -826, 568, -495, -855, 778, -963, 433, -260, -391}

    Returns: 41

  49. {833, -554, 23, -967, -114}

    Returns: 4

  50. {-990,-950,-939,-931,-916,-892,-825,-787,-652,-649,-607,-552,-544,-543,-514,-388,-319,-304,-233,-176,-158,-89,-55,5,24,57,58,75,175,177,187,205,240,260,276,312,484,499,594,612,618,680,715,750,822,930,933,985,990,999}

    Returns: 0

  51. {934,917,847,819,805,804,720,664,620,592,562,498,475,462,393,340,319,305,251,237,226,216,202,118,78,65,16,-22,-43,-96,-113,-119,-264,-267,-298,-340,-341,-495,-593,-643,-650,-693,-706,-716,-731,-805,-815,-938,-952,-994}

    Returns: 49

  52. {982,-993,-872,-855,-840,-798,-743,-728,-686,-667,-642,-637,-629,-562,-446,-379,-375,-368,-363,-320,-284,-272,-192,-136,-111,-100,-95,-89,-49,5,27,43,64,286,398,536,546,568,634,758,763,785,796,812,897,898,925,961,964,-1000}

    Returns: 49

  53. {-745,-706,269,-279,990,-734,690,473,-278,-546,970,586,-499,-994,-580,588,-157,349,-228,435,950,-806,385,359,-939,-597,-576,153,274,-714,809,759,78,891,755,-915,170,134,87,-878,250,-134,-301,-96,115,-548,-865,651,788,218}

    Returns: 45

  54. {-223,-499,-550,-486,421,-609,-36,-985,345,-948,-63,713,-992,-838,-193,613,-882,968,-428,933,-237,125,49,765,215,-615,-880}

    Returns: 26

  55. {-510,788,-434,-629,-653,-725,-997,436,-258,776,-968,476,397,541,-75,91,681,823,-999,591,576,-851,-802,-783,559,721,-543,-68,157,729,122,-52,539,-460,-506,-298,-706,871,780,-299,133}

    Returns: 40

  56. {-102,254,898}

    Returns: 0

  57. {391,-273,637,134,-707,-461,-539,-706,862,448,889,-743,-39,43,-274,-678,935,-711,-620,496,164,-892,257,314,-422,368,-332,-198,-408,-358,376,500,-843,259}

    Returns: 32

  58. {437,-605,216,22,747,-626,918,219,455,-307,967,-218,-711,-520,668,823,-49,870,287,-772,-132,324,-601,521,-640,-473}

    Returns: 25

  59. {67,271,-453,138,402,969,2,-265,884,842,212,-458,-543,839,-798,499,-80,-821,-269}

    Returns: 18

  60. {-923,253,445,-308,892,446,-960,-304,521,-793,-669,460,-776,-297,831,791,-376,-735,-624,301,203,2,-900,-195,-425,-221,-714,135,714,-38,665,-218,5,672,-350,-722,-639,299,-92,731,17,-528,600}

    Returns: 42

  61. {441,-382,-743,-65,-29,-774,-453,-922,-813,969,-619,755,-565,482}

    Returns: 12

  62. {311,129,102,-18,-152,-558,-874,-709}

    Returns: 6

  63. {315,312,698,30,-702,156,420,-319,-467,-481,306,-457,-581,313,-205,912,-720,-326,977,443,77,-161,794,670,-957,-218,332,-736,292,-33,-782,-327,803}

    Returns: 31

  64. {356,-824}

    Returns: 1

  65. {67,758,-693,333,-59,-583,-368,841,-589,-643,-967,-579,-876,910,967,500,-873,490,-67,257,461,882,730,-859,255,229,-187,736}

    Returns: 24

  66. {-968,-567,-621}

    Returns: 1

  67. {308,-106,-939,-179,-420,906,-192,801,589,-436,-38,378,622,110,-798,-113,-214,-320,633,313,548,298,572,-654,-506,885,-94,-356}

    Returns: 24

  68. {250,-225,251,142,264,-837,847,196,587,568}

    Returns: 9

  69. {589,-145,718,-174,652,619,422,699,-397,-147,-288,365,478,-268,425,-903,75,420,731,-772,317,-532,-17,-614,801,613,-599,-738,-6,442,-68,626,314,-487,780,970,653,510,-81,-727,-308,-908}

    Returns: 41

  70. {575,-43,-159,-289,-211,346,290,-256,678,760,70,-477,62,-462,-216}

    Returns: 13

  71. {-328,-37,-593,650,-738,524,-807,-855,304,867,-466,-620,-799,-291,539,814,-251,493,781,-9,-901,-908,-868,480,-158,233,-590,141,206,463,259,-747,221,145,816,-15,-503,-198,126,230,704,310,-299,353}

    Returns: 43

  72. {869,424,471,-262,402,767,526,-656,345,-264,705,25,-714,-431,920,-602,-318,60,-436,-801,-449,905}

    Returns: 21

  73. {-605,-662,43,-793,842,529,697,-846,-328,-131,280,13,-466}

    Returns: 12

  74. {10,-476,-122,-125,566,481,-368,-346,517,323,810,32,-801,447,-387,571,-150,376,72,-48,-40,-66,-683,375,-147}

    Returns: 23

  75. {687,686,-984,619,-909,811,755,-428,-961,-243,928,-155,395,-952,-734,-358,-185,-87,-167}

    Returns: 16

  76. {722,346,-297,-926,-873,-615,240,-11,422,-919,-938,31,901,-434,141,-630,476,621,743,641,325,-753,573,-511,-894,-968,710,-942,894,-153,-891,730,-39,257,-319}

    Returns: 33

  77. {-901,677,546,211,-911,-698}

    Returns: 5

  78. {-874,847,-478,786,814,861,656,-695,983,168,284,-979,-253,676,-142,398,647,-483,451,226,-484,-168,859,715,866,102,-586,-624,-661,762,-213,-793,267,758,-592,-680,336,-830,-540}

    Returns: 38

  79. {378,-564,-100,-727,-243,178,-212,-482,314,-642,326,423,-58,171,611,525,-248,-164,342,224,655,954,603,-743,646,622,775,-405,569,816,-40,297,-262,991,-930,772,739,105,161,-583,26,8,485,-850,707,-352,-434}

    Returns: 45

  80. {-932,767,223,505,697,381,458,335,-836,540,-817,757,-400,-747,422,-77,-652,488,878,-342,-724,-806,234,-573,764,-313,-769,-160,760,-580,380,-291,307,-799,582,-823,300,653,167,111}

    Returns: 37

  81. {-829,-669,468,545,-456,558,366,540,942,-922,-371,-949,-221,937,-265,-927,-720,-24,515,404,500,-326,-548,494,-84,180,-20,266}

    Returns: 26

  82. {-274,581,733,60,-871,1,869,-734,-702,8,770,-298,553,-268,870,-76,-209,432,913,364,798,889,-502,343}

    Returns: 20

  83. {1, 3, 4, 5, 6, 7, 8, 9, 2 }

    Returns: 7

  84. {-2, -8, 9, 0 }

    Returns: 3

  85. {976, -946, -824, 680, -644, -95, 128, -892, 816, -263, -592, -669, 887, 447, -653, -759, 572, 171, 635, 98, -904, 78, 143, -416, -40, -846, 784, -702, -738, -858, 582, 603, -535, 529, 84, -964, 934, 36, 783 }

    Returns: 38

  86. {5, 1, 2, 3, 4 }

    Returns: 1

  87. {5 }

    Returns: 0

  88. {976, -946, -824, 680, -644, -95, 128, 129, 816, -263, -592, -669, 887, 447, -653, -759, 572, 171, 635, 98, -904, 78, 143, -416, -40, -846, 784, -702, -738, -858, 582, 603, -535, 529, 84, -964, 934, 36, 783 }

    Returns: 38

  89. {180, 20, -270, 480, -110, 100, -10, -330, 260, -130, -30, -170, 360, -430, -450, -150, 380, -490, 460, -350, 160, 440, -230, -290, -410, 60, -210, -50, 400, -90, -370, 120, 340, 200, -310, -190, 240, 220, -470, 320, 300, -250, 140, 0, -70, 280, -390, 420, 80, 40 }

    Returns: 48

  90. {-2, -1, -10, 5 }

    Returns: 3

  91. {10, 2, 4, 7, -11, -101, 9, 8, 6, 999, 998, 997, -999, -998, -997, 123, 124, 125, -123, -122, -111 }

    Returns: 15

  92. {976, -946, -824, 680, -644, -95, 128, -892, 816, -263, -592, -669, 887, 447, -653, -759, 572, 171, 635, 98, -904, 78, 143, -416, -40, -846, 784, -702, -738, -858, 582, 603, -535, 529, 84, -964, 934, 36, 783, 53 }

    Returns: 39

  93. {4, 7, 1, 2, 3, 5 }

    Returns: 3

  94. {-2, -8, 9, 0, 443, -33, 67, 22 }

    Returns: 7

  95. {1, 2, 3, 4, 5 }

    Returns: 0

  96. {976, -94, -82, 68, -644, -95, 128, -892, 216, 263, -592, -669, 887, 447, -653, 759, 57, 171, 635, 98, -904, 78, 14, 416, -40, -846, 784, -702, -738, -858, 582, 603, -535, 529, 84, -964, 934, 36, 783 }

    Returns: 38

  97. {976, -94, -2, 68, -644, -95, 128, -892, 216, 263, -592, -669, 887, 447, -653, 759, 57, 171, 635, 98, -904, 78, 14, 416, -40, -846, 784, -702, -738, -858, 582, 603, -535, 529, 84, -964, 934, 36, 783, 123, 432, 0, -11, -21 }

    Returns: 43

  98. {1, 50, 2, 49, 3, 48, 4, 47, 5, 46, 6, 45, 7, 44, 8, 43, 9, 42, 10, 41 }

    Returns: 9

  99. {10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

    Returns: 9

  100. {-1, 2, 3, 4, 5, -5, -6, -3, -2, 100, 101, 99, -1000, -999 }

    Returns: 12

  101. {1, 2, 6, 9, 3, 4, 5 }

    Returns: 2

  102. {15, 4, 88, 6, 999, 65, 33 }

    Returns: 5

  103. {7, 8, 9, 2 }

    Returns: 3

  104. {1, 2, 40, 30, 50 }

    Returns: 2

  105. {2, 4, 56, 54, 53, 3, 57, 58, 59, 1, 21, 22, 23, 20, 100 }

    Returns: 14

  106. {2, 4, 3, 1 }

    Returns: 3

  107. {1, 4, 5, 6, 7, 8, 3, 2, 9 }

    Returns: 7

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: