Statistics

Problem Statement for "InsertionSortCount"

Problem Statement

A sequence of distinct numbers A is going to be sorted using insertion sort. Insertion sort works as follows:

insertion-sort(A)
   initialize a new empty sequence R
   for each number N in A (in the original order) do:
      determine the index i in R where N should be inserted so that R remains sorted
      move each element in R with index greater than or equal to i to the following index
      set R[i]=N
   return R

For example, an insertion sort on {20,40,30,10} would produce the following states for R after each step:
20 (first element is inserted at index 0)
20,40 (inserting 40 at index 1 requires no moves)
20,30,40 (30 is inserted at index 1, so 40 has to be moved)
10,20,30,40 (10 is inserted at index 0, so 20, 30 and 40 have to be moved)
In total, 4 moves were needed.

Given a int[] A, which contains a sequence of distinct numbers, return the number of moves that would be performed by an insertion sort on A.

Definition

Class:
InsertionSortCount
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. {20,40,30,10}

    Returns: 4

    The example from the problem statement.

  2. {-1,1,0}

    Returns: 1

    Only one move needed to insert 0.

  3. {-1000,0,1000}

    Returns: 0

    Since elements are inserted in sorted order, all of them are appended at the end of R. Therefore, there's no need to move anything.

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

    Returns: 0

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

    Returns: 45

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

    Returns: 9

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

    Returns: 9

  8. {-1000,1000,0}

    Returns: 1

  9. {1000,-1000,0}

    Returns: 2

  10. {1000,0,-1000}

    Returns: 3

  11. {0,-1000,1000}

    Returns: 1

  12. {0,1000,-1000}

    Returns: 2

  13. {325}

    Returns: 0

  14. {-1000}

    Returns: 0

  15. {234,654,747,34,37,-37,43,235,5,35,674,-23,6,4,454,3,53,354,23}

    Returns: 98

  16. {-989,-986,-829,-821,-749,-716,-683,-606,-540,-520,-411,-410,-400,-385,-366,-357,-353,-310,-8,0,78,104,116,118,221,224,261,301,351,434,445,453,482,486,501,509,577,585,600,630,636,654,723,786,809,867,886,938,950,966}

    Returns: 0

  17. {952,923,828,757,695,656,588,571,557,547,333,319,305,269,245,217,156,154,152,134,133,72,71,39,23,-3,-40,-135,-166,-176,-218,-363,-389,-442,-466,-476,-488,-512,-518,-551,-582,-593,-620,-629,-659,-744,-749,-753,-822,-880}

    Returns: 1225

  18. {-861,-726,-571,-691,-725,-564,-527,-381,672,778,348,271,279}

    Returns: 11

  19. {-957,-956,-896,-122,-688,-626,-625,-419,-417,38,-410,-389,-382,-357,-253,-186,-155,-818,-48,-19,-415,902,234,244,319,498,499,607,649,822,679,678,752,664,177}

    Returns: 79

  20. {-210,493,-402,-121,474,-340,617}

    Returns: 8

  21. {-984,-980,-916,-892,-813,9,-709,-693,-656,-615,-539,-481,-453,-381,-312,-280,-274,-258,-139,-133,870,371,-74,-33,-18,-781,123,275,308,-80,481,549,758,-114,933,954}

    Returns: 75

  22. {-937,-912,-818,-629,-618,-589,-406,-330,-221,-183,184,-107,-34,-19,19,33,-143,220,256,321,325,336,342,354,358,395,426,466,474,479,715,764,836,936,966,967}

    Returns: 11

  23. {17,-734,-619,-923,671}

    Returns: 5

  24. {-960,-763,-745,-704,-604,-491,-490,-396,-381,817,-246,-177,-16,12,70,90,191,232,313,322,374,506,569,590,607,632,660,678,684,716,801,802,-308,849,865,913,931,990}

    Returns: 45

  25. {-915,-845,-747,-640,-523,-505,-475,-402,-364,-342,-332,-308,-250,-242,-212,77,326,962,733,754,332,1000}

    Returns: 5

  26. {-898,-852,-843,-648,-497,-350,-212,678,-171,-134,758,-8,124,70,71,97,17,286,-204,714,-120,837,842}

    Returns: 45

  27. {-910,-847,-738,-386,-320,-316,-278,-15,-3,57,283,390,643,971,978}

    Returns: 0

  28. {967,931,918,878,874,791,781,780,773,756,743,687,-972,590,495,477,467,289,200,174,123,120,677,47,73,-231,-293,-298,-305,-309,-366,-400,-512,-865,-713,-745,-844,-595,-966,-126}

    Returns: 722

  29. {821,716,604,-640,297,278,246,237,195,-13,-29,-38,-217,-738,380,-659,-724,-541,-794,-822,-953,-959}

    Returns: 205

  30. {644,-960}

    Returns: 1

  31. {906,892,864,835,819,753,710,573,-442,419,203,394,368,331,260,413,165,64,-45,-48,-87,-130,-142,-174,-183,-197,-198,-244,-316,-379,-404,-453,-412,461,-452,-408,-559,-570,-640,-662,-699,-705,-712,-747}

    Returns: 883

  32. {973,924,896,837,803,790,743,733,700,615,586,527,521,477,475,306,297,250,222,179,131,99,68,41,-44,-67,-158,-274,-277,-290,-322,-487,-528,-545,-546,-694,-816,-825,-847,-941,-963,-974}

    Returns: 861

  33. {963,945,944,-577,843,779,759,725,586,480,479,472,422,391,312,165,81,60,36,-157,-232,-352,872,-602,-812}

    Returns: 263

  34. {647,591,554,434,-269,-456,-75,-102,-137,206,-350,127,-546,-653,-742,-796,-883}

    Returns: 118

  35. {992,969,930,894,836,835,-831,797,795,832,693,649,449,98,28,-77,-141,-142,-393,-510,-574,-663,-726,792,-956}

    Returns: 268

  36. {928,927,655,-87,631,473,411,193,116,-14,-179,-165,642,-303,-919,-931}

    Returns: 104

  37. {954,752,595,570,264,191,0,-57,-159,-298,-511,-730,-762,-764,-799,-857,-942}

    Returns: 136

  38. {937,-893,-888,-868,-865,-838,-801,-742,-690,-595,-478,-444,-422,-415,-331,-319,-289,-283,-263,-222,-209,-181,-165,-134,-116,-73,3,18,19,133,170,183,207,301,334,387,437,448,482,523,642,696,707,722,753,788,791,792,806,884}

    Returns: 49

  39. {-909,-883,-855,-851,-843,-801,-751,-690,-674,-647,-602,-560,-481,-419,-399,-360,-351,-350,-344,-341,-258,-221,-216,-176,-103,-60,49,124,154,155,161,169,212,227,313,370,437,523,527,538,566,628,760,782,797,817,823,849,941,-927}

    Returns: 49

  40. {1000,-909,-887,-885,-728,-659,-635,-471,-454,-452,-428,-421,-399,-367,-362,-353,-315,-284,-243,-228,-224,-129,-123,-116,-27,-15,13,82,161,198,286,306,309,328,340,384,403,440,471,473,576,602,605,688,715,772,855,871,947,-1000}

    Returns: 97

  41. {139,892,639,-196,551,730,-751,14,-965,-381,-634,-838,492,207,192,-790,952,-155,664,722,-815,-224,196,157,-51,963,-932,-181,-302,-973,-282,-770,-60,-765,-395,-972,926,-860,-688,960,40,514,406,248,-654,-833,-341,-892,-776,986}

    Returns: 692

  42. {-830,-749,-35,659,592,-908,511,715,837,401,862,-96,180,-356,820,-348,-630,-65,-603,475,-363,268,-519,897,430,641,719,347,-756,-250,-721}

    Returns: 239

  43. {806,997,-605,-277,652,281,661,204,133,-826,872,-323,92,-17,-629,930,-842,327,-265,884,214,-160,-558,860,-159}

    Returns: 168

  44. {-313,768,-288,691,590,144,-49,-373,980,16,390,289}

    Returns: 32

  45. {-39,132,178,323,-642,-922,-250,-316,739,681,-861,186,240,489,165,-842,57,500,918,-867,936,828,950,-352,561,-390,148,955,-204,-374,-636,-118,652,-820,-538,-682,793}

    Returns: 329

  46. {-489,129,419,-116,494,982,66,-226,292,-172,698,765,381,386,-587,32,-315,-344,708,927,-965,-156,-595,238,537,-416,836,215,72,-543,719,-924,-244,-18,-472,220,-649,738,-443,502,790,867,-523,731,-471,213,112,-300,-292,-94}

    Returns: 653

  47. {311,-782}

    Returns: 1

  48. {-654,47,-461,-594,473,113,739,557,850,-550,-852,-227,-523,791,-721,493,333,-607,-106,278,-679,918,-601,652,208,-888,391,579,-482,-216,590,818,402,209,-204,-217,408,351,-182,620,-944,-969,539,-300,190,274,-209,-54,-533,-614}

    Returns: 631

  49. {872,877,825,-797,821,-791,180,-251,156,-944,-356,-430,-992,201,-619,-257,943,250,-990,-334,-183,-729,896,111,-223,892,-80,-269,-807,502,494,-914,260,-513,81,-457,-60,940,-870,330,-925,-21,620,533,534}

    Returns: 479

  50. {-687,448,-104,825,-143,-397,756,307,988,546,781,957,-721,-589,898,361,-891,-871,-202,-256,-543,-3,-170,532}

    Returns: 153

  51. {-880,-401,-883,-170,227,-759,818,542,255,1,-52,-780,-365,188,-885,-337,651,229,552,-728,623,621}

    Returns: 85

  52. {-627,618,629,853,-752,-184,-948,430,435,-228,643,-882,-202,-863,373,504,-816,-675,-906,-352,131,-99,783,-918,896,-370,877,-639,-572,803,271,417,422,723,-212,-876,-664,179,912,-700,-41,197,-735,-424,358,132}

    Returns: 512

  53. {-91,372,107,-330,913,465,-338,316,670,403,-555,-227,759,-499,766,-665,689}

    Returns: 68

  54. {-993,114,-323,-665,-672,-577,-133,-996,194,-299,-431,637,-253,-832,973,306,647,40,-999,-986,606,-329,-987,-269,419,545,-803,-228,720,-784,-155,-961,693,-474,-432,-52,-597,-78,-318,275}

    Returns: 349

  55. {-52,646,299,-605,-2,750,885,-963,-615,-1000,-976,551,653,968,363,-167,-258,27,924,289,135,462,523,-524,605,-197,303,39,-920,-552,-687,-4,935,-955,-134,201,948,-957,499,-689,-408}

    Returns: 446

  56. {987,125,831,117,-167,-67,67,-98,-438,262,773,507,-909,554,-923,-830,-252,-144,30,-284,668,489,-444,-622,253,921,334,687,-775,-251,-590,-138,-145,890,-660,-95,857,-270,197,25,612,-986,606,563,-169,319,878,-73,-669,201}

    Returns: 621

  57. {-505,865,587,86,-431,-120,678,-387,425,898,1000,-191,937,-508,-261,126,-736,-837,239,980,-187,288,-426,361,866,713,-755,-162,374,910}

    Returns: 207

  58. {608,753,-947,-100,-713,531,-190,224,85,-361,-230,669,-963,923,-389,-740,301,-189,-135,368,612,433,-819,-480,187,561,549,-31,-112,575,-984,-951,-812,-447,484,-927,-538,-33,703,23}

    Returns: 415

  59. {693,-461,-675,705,39,608,820,-379,440,628,-245,-771,519,195,-507,-391,173,501,-856,779,186}

    Returns: 115

  60. {12,-221,-143,-671,-177,-482,835,-495,21,127,618,-526,-326,-689,-521,-431,-621,-531,437,507,-75,308,323,-355,368,-841,-941,-641,287,628,723,-349,-583,-860,-421,731,211,-584,-509,242,787,192,-901,-738,-965,753}

    Returns: 535

  61. {-671}

    Returns: 0

  62. {952,-174,-93,-380,759,-894,543,-734,-913,-957,279,-228,-186,902,366,-643,213,-102,243,-941,-612,-761}

    Returns: 136

  63. {237,552,605,-616,-540,-58,-360,-839,-672,-274,-144,537,830,-814,-703,554,463,879,-959,-423,-293,479,577,-507,115,-206,-676,-917,987,307,962,-6,-951,66,623,442,-435,356,75,545,-620,746}

    Returns: 391

  64. {238,942,906}

    Returns: 1

  65. {647,-692,-66,-532,892,300,-585,54,-965,297,545}

    Returns: 27

  66. {-444,3,-358,314,-578,-577,-453,154,817,595,-594,198,-570,120,-506,-604,-744,-105,-887,-755,115,-522,-819,310,790}

    Returns: 170

  67. {-563,968,825,-445,-527,258,-359,528,261}

    Returns: 16

  68. {-203,930,908,338,-794,-688,570,-207,-475,-36,700,-6,-29}

    Returns: 41

  69. {606,713,-449,124,193,380,-53,322,-332,-194,771,597,333,58,-59,-941,-426,-363,39,930,488,-76,-324,-380,111,-868,-719,962,359}

    Returns: 235

  70. {-601,713,67,476,-933,-499,441,-263,-172,195,-724,793,322,-813,404,584,935,771,-52,612,873,606,-394,746,-69,46,-275,454,-965,-544,985,-811,-615,738,-927,10,-94,678,443,528,-400,689,181,-989,-824,823,-473,555,103,342}

    Returns: 617

  71. {-955,412,251,315,-871,307,978,-648,-488,-163,-658,-281,484,349,452,434,980,-264,-467,-296,-883,-708,-387}

    Returns: 133

  72. {-567,772,-124,-674,-213,-865,962,666,11,-374,-916,-28,-944,479,-507,257,-818,-463}

    Returns: 87

  73. {-83,486,-369,-184,-257,760,-365,19,140,396,901,-222,-410,-466,599,957,514,-608,226,49,-70,-113,671,-995,120,645,866,-568,-610,-656,317,-505,-750,-776}

    Returns: 335

  74. {-795,197,343,492,943,309,-815,-201}

    Returns: 14

  75. {-898,-268,-294,559,456,566,-303,862,-301,936,-8,247,-871,-239,837,-123,-823,72,207,363,860,684,666,-956,-117,-655,-197,831,757,963,-763,976,416,-792,-158,152,-617}

    Returns: 314

  76. {150,-822,368,-364,214,577,-550,-169,-864,412,830,769,751,637,818,608,-17,-306,-615,-570,86,557,27,-367,-693,825,408,94,21,237,148,654,319,-73}

    Returns: 271

  77. {-524,672,4,282,-470,-961,650,-192,188,158,369,-381,-277,-486,678,49,-34,-553,70,-660,719,417,882,253}

    Returns: 120

  78. {-123,-945,-285,606,-394,-196,987,53,-832,-132,146,-654,653,-920,958,-641,926,-816,-855,-969}

    Returns: 107

  79. {-865}

    Returns: 0

  80. {961,112,113,-468,526,-962,893,-256,10,-655}

    Returns: 30

  81. {1,3,5,7,9,11,13,15,17,19,21,2,4,6,8,10,12,14,16,18,20}

    Returns: 55

  82. {20, 40, 30, 10 }

    Returns: 4

  83. {-5, -4, -2, 0, 6, 7 }

    Returns: 0

  84. {-1000, 0, 1000, 99, -99 }

    Returns: 4

  85. {25, 10, 38, 1, 89, 6 }

    Returns: 8

  86. {20, 10 }

    Returns: 1

  87. {90, 45, 70, 30, 15, 86, 34, 512, -1000, 433 }

    Returns: 23

  88. {-1, 1, 0, 4, 5, 6, 76, 12, 78, 89, 56, 45, 343, 232, 454, 565 }

    Returns: 10

  89. {3, 2, 1, 4 }

    Returns: 3

  90. {2, 8, 9, 11, 5, 10 }

    Returns: 4

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: