Statistics

Problem Statement for "UnsortedSequence"

Problem Statement

We say that the sequence of numbers {s[0], s[1], s[2], ..., s[N-1]} is sorted in ascending order if we have s[i] <= s[i+1] for each i between 0 and N-2, inclusive.


For example, the sequences {1,2,3}, {1,1,1}, and {2,2,4,4,6,6} are sorted in ascending order, but the sequences {1,2,1}, {7,4,6}, and {3,2,1} are not.


You are given the sequence of numbers as a int[] s. Your task is to order the elements of this sequence into a sequence that will NOT be sorted in ascending order. Find and return the lexicographically smallest sequence we can obtain. If there is no possibility to get a sequence that is not sorted in ascending order, return an empty int[] instead.

Definition

Class:
UnsortedSequence
Method:
getUnsorted
Parameters:
int[]
Returns:
int[]
Method signature:
int[] getUnsorted(int[] s)
(be sure your method is public)

Notes

  • Sequence of numbers A is lexicographically smaller than B if A contains a smaller number on the first position on which they differ.
  • The sequence s may contain duplicates.
  • Note that the sequence consisting of only one element is always sorted.

Constraints

  • s will contain between 1 and 50 elements, inclusive.
  • Each element of s will be between 1 and 1000, inclusive.

Examples

  1. {1,2}

    Returns: {2, 1 }

    There is only one possible sequence that is not in ascending order: {2,1}.

  2. {1,2,3}

    Returns: {1, 3, 2 }

    Out of all six possible sequences, five are not in ascending order. Here they are, in lexicographic order: {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

  3. {7,2,2}

    Returns: {2, 7, 2 }

    Remember, that the given sequence may contain duplicates.

  4. {1000}

    Returns: { }

    As mentioned in the Notes section, the sequence consisting of only one element is always sorted. So there is no possibility to unsort this sequence.

  5. {1,1}

    Returns: { }

    There are also some longer sequences that cannot be unsorted.

  6. {1,2,4,3}

    Returns: {1, 2, 4, 3 }

  7. {1,1,1,1}

    Returns: { }

  8. {2,1,1,1}

    Returns: {1, 1, 2, 1 }

  9. {1,2,1,1}

    Returns: {1, 1, 2, 1 }

  10. {2,2,1,1}

    Returns: {1, 2, 1, 2 }

  11. {1,1,2,1}

    Returns: {1, 1, 2, 1 }

  12. {2,1,2,1}

    Returns: {1, 2, 1, 2 }

  13. {1,2,2,1}

    Returns: {1, 2, 1, 2 }

  14. {2,2,2,1}

    Returns: {2, 1, 2, 2 }

  15. {1,1,1,2}

    Returns: {1, 1, 2, 1 }

  16. {2,1,1,2}

    Returns: {1, 2, 1, 2 }

  17. {1,2,1,2}

    Returns: {1, 2, 1, 2 }

  18. {2,2,1,2}

    Returns: {2, 1, 2, 2 }

  19. {1,1,2,2}

    Returns: {1, 2, 1, 2 }

  20. {2,1,2,2}

    Returns: {2, 1, 2, 2 }

  21. {1,2,2,2}

    Returns: {2, 1, 2, 2 }

  22. {2,2,2,2}

    Returns: { }

  23. {1,100,100,1000}

    Returns: {1, 100, 1000, 100 }

  24. {1,100,1000,100}

    Returns: {1, 100, 1000, 100 }

  25. {1,1000,100,100}

    Returns: {1, 100, 1000, 100 }

  26. {100,1,100,1000}

    Returns: {1, 100, 1000, 100 }

  27. {100,1,1000,100}

    Returns: {1, 100, 1000, 100 }

  28. {100,100,1,1000}

    Returns: {1, 100, 1000, 100 }

  29. {100,100,1000,1}

    Returns: {1, 100, 1000, 100 }

  30. {100,1000,1,100}

    Returns: {1, 100, 1000, 100 }

  31. {100,1000,100,1}

    Returns: {1, 100, 1000, 100 }

  32. {1000,1,100,100}

    Returns: {1, 100, 1000, 100 }

  33. {1000,100,1,100}

    Returns: {1, 100, 1000, 100 }

  34. {1000,100,100,1}

    Returns: {1, 100, 1000, 100 }

  35. {468,335,501,170,725,479,359,963,465,706,146,282,828,962,492,996,943,828,437,392,605,903,154,293,383,422,717,719,896,448,727,772,539,870,913,668,300,36,895,704,812,323}

    Returns: {36, 146, 154, 170, 282, 293, 300, 323, 335, 359, 383, 392, 422, 437, 448, 465, 468, 479, 492, 501, 539, 605, 668, 704, 706, 717, 719, 725, 727, 772, 812, 828, 828, 870, 895, 896, 903, 913, 943, 962, 996, 963 }

  36. {674,665,142,712,254,869,548,645,663,758,38,860,724,742,530,779,317,36,191,843,289,107,41,943,265,649,447,806,891,730,371,351,7,102}

    Returns: {7, 36, 38, 41, 102, 107, 142, 191, 254, 265, 289, 317, 351, 371, 447, 530, 548, 645, 649, 663, 665, 674, 712, 724, 730, 742, 758, 779, 806, 843, 860, 869, 943, 891 }

  37. {549,630,624,85,955,757,841,967,377,932,309,945,440,627,324,538,539,119,83,930,542,834,116,640,659,705,931,978,307,674,387,22,746,925,73,271,830,778,574,98,513,987,291,162}

    Returns: {22, 73, 83, 85, 98, 116, 119, 162, 271, 291, 307, 309, 324, 377, 387, 440, 513, 538, 539, 542, 549, 574, 624, 627, 630, 640, 659, 674, 705, 746, 757, 778, 830, 834, 841, 925, 930, 931, 932, 945, 955, 967, 987, 978 }

  38. {356,768,656,575,32,53,351,151,942,725,967,431,108,192,8,338,458,288,754,384,946,910,210,759,222,589,423,947,507,31,414,169,901,592,763,656,411}

    Returns: {8, 31, 32, 53, 108, 151, 169, 192, 210, 222, 288, 338, 351, 356, 384, 411, 414, 423, 431, 458, 507, 575, 589, 592, 656, 656, 725, 754, 759, 763, 768, 901, 910, 942, 946, 967, 947 }

  39. {625,538,549,484,596,42,603,351,292,837}

    Returns: {42, 292, 351, 484, 538, 549, 596, 603, 837, 625 }

  40. {21,597,22,349,200,669,485,282,735,54,1000,419,939,901,789,128,468,729,894,649,484,808,422,311,618}

    Returns: {21, 22, 54, 128, 200, 282, 311, 349, 419, 422, 468, 484, 485, 597, 618, 649, 669, 729, 735, 789, 808, 894, 901, 1000, 939 }

  41. {515,310,617,936,452,601,250,520,557,799,304,225,9,845}

    Returns: {9, 225, 250, 304, 310, 452, 515, 520, 557, 601, 617, 799, 936, 845 }

  42. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: { }

  43. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: { }

  44. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 49 }

  45. {50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 49 }

  46. {1,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

    Returns: {50, 1, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

  47. {50,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 50, 1 }

  48. {2,2,1,2,2,2,2,2,2,1,2,1,1,1,1,1,1,1,2,2,1,2,2,1,1,1,1,1,2,1,2,1,2,2,1,1,2,1,1,1,2,1,1,1,1,2,2,2,1,1}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  49. {1,2,1,1,2,2,2,2,1,1,2,2,1,1,1,2,2,2,1,2,2,2,2,1,2,1,2,1,1,2,2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,2,1,1}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  50. {2,2,2,2,1,2,2,2,2,1,2,2,2,2,1,1,2,1,1,2,1,1,2,1,2,1,2,2,2,2,2,1,1,1,2,2,1,2,1,1,1,2,1,1,1,2,2,2,1,2}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  51. {467,45,660,293,440,254,25,155,511,746,650,187,314,475,23,169,19,788,906,959,392,203,626,478,415,315,825,335,875,373,160,834,71,488,298,519,178,774,271,764,669,193,986,103,481,214,628,803,100,528}

    Returns: {19, 23, 25, 45, 71, 100, 103, 155, 160, 169, 178, 187, 193, 203, 214, 254, 271, 293, 298, 314, 315, 335, 373, 392, 415, 440, 467, 475, 478, 481, 488, 511, 519, 528, 626, 628, 650, 660, 669, 746, 764, 774, 788, 803, 825, 834, 875, 906, 986, 959 }

  52. {626,544,925,24,973,62,182,4,433,506,594,726,32,493,143,223,287,65,901,188,361,414,975,271,171,236,834,712,761,897,668,286,551,141,695,696,625,20,126,577,695,659,303,372,467,679,594,852,485,19}

    Returns: {4, 19, 20, 24, 32, 62, 65, 126, 141, 143, 171, 182, 188, 223, 236, 271, 286, 287, 303, 361, 372, 414, 433, 467, 485, 493, 506, 544, 551, 577, 594, 594, 625, 626, 659, 668, 679, 695, 695, 696, 712, 726, 761, 834, 852, 897, 901, 925, 975, 973 }

  53. {465,120,153,801,88,61,927,11,758,171,316,577,228,44,759,165,110,883,87,566,488,578,475,626,628,630,929,424,521,903,963,124,597,738,262,196,526,265,261,203,117,31,327,12,772,412,548,154,521,791}

    Returns: {11, 12, 31, 44, 61, 87, 88, 110, 117, 120, 124, 153, 154, 165, 171, 196, 203, 228, 261, 262, 265, 316, 327, 412, 424, 465, 475, 488, 521, 521, 526, 548, 566, 577, 578, 597, 626, 628, 630, 738, 758, 759, 772, 791, 801, 883, 903, 927, 963, 929 }

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

    Returns: {1, 2, 2, 2, 3, 5, 5, 5, 6, 6, 8, 8, 9, 10, 9, 10, 10 }

  55. {1, 2, 3 }

    Returns: {1, 3, 2 }

  56. {1000, 1, 1, 1, 1, 1, 1, 1, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 1, 1, 1 }

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 1000, 3, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

  57. {2, 2, 2, 2, 2 }

    Returns: { }

  58. {1, 1, 1, 1 }

    Returns: { }

  59. {1, 2, 3, 4 }

    Returns: {1, 2, 4, 3 }

  60. {1000 }

    Returns: { }

  61. {1 }

    Returns: { }

  62. {4, 4, 4 }

    Returns: { }

  63. {1, 1, 1 }

    Returns: { }

  64. {1, 1 }

    Returns: { }

  65. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 }

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 26 }

  66. {3, 2, 1 }

    Returns: {1, 3, 2 }

  67. {5, 5, 3, 5, 3, 5 }

    Returns: {3, 5, 3, 5, 5, 5 }

  68. {1, 2, 2 }

    Returns: {2, 1, 2 }

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

    Returns: {1, 2, 2, 2, 3, 5, 5, 5, 6, 6, 8, 8, 9, 10, 9, 10, 10 }

  70. {1, 2 }

    Returns: {2, 1 }

  71. {2, 1 }

    Returns: {2, 1 }

  72. {1, 1, 1, 1, 1, 1 }

    Returns: { }

  73. {7, 7, 2, 2, 2 }

    Returns: {2, 2, 7, 2, 7 }

  74. {3, 1, 2, 2 }

    Returns: {1, 2, 3, 2 }

  75. {10, 10, 1, 2 }

    Returns: {1, 10, 2, 10 }

  76. {2, 1, 1, 1 }

    Returns: {1, 1, 2, 1 }

  77. {2, 2, 2 }

    Returns: { }

  78. {2, 2 }

    Returns: { }

  79. {1, 1, 2, 2, 3, 3, 5, 67, 78, 78, 78, 89, 89, 89 }

    Returns: {1, 1, 2, 2, 3, 3, 5, 67, 78, 78, 89, 78, 89, 89 }

  80. {2, 2, 3, 3, 3, 7, 7, 7 }

    Returns: {2, 2, 3, 3, 7, 3, 7, 7 }

  81. {2, 1, 2 }

    Returns: {2, 1, 2 }

  82. {5, 5, 5, 5 }

    Returns: { }

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

    Returns: {1, 2, 2, 2, 3, 5, 5, 5, 6, 6, 8, 8, 9, 9, 10, 10, 11, 10 }

  84. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 50, 11, 20, 23, 76, 34, 23, 76, 1, 4, 1, 7, 3, 2, 7, 2, 8, 5, 3, 5, 2, 5, 2, 6, 3, 9, 7, 5, 4, 1, 6, 4, 2, 5, 8, 5, 3 }

    Returns: {1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 10, 11, 11, 12, 20, 23, 23, 34, 76, 50, 76 }

  85. {1, 2, 3, 3, 3, 3 }

    Returns: {1, 3, 2, 3, 3, 3 }

  86. {1, 3, 2 }

    Returns: {1, 3, 2 }

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

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

  88. {2, 7, 7 }

    Returns: {7, 2, 7 }

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

    Returns: {1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 9, 78, 32 }

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: