Statistics

Problem Statement for "SwappingNodes"

Problem Statement

We have a full binary tree. That is, we have a rooted tree in which all leaves have the same depth, and each node that is not a leaf has exactly one left child and one right child. Each leaf of our tree contains a positive integer, and these integers are distinct.

As an example, the figure below shows a full binary tree with four leaves: 

                              ________C________
                             /                 \
                        ____A____           ____B____ 
                       /         \         /         \
		      5 	  2       1           3

You are given the int[] leaves: the values that are currently stored in the leaves of the tree, read from the left to the right. For example, for the tree shown above you would be given leaves = {5, 2, 1, 3}.

For your convenience, you are also given the int numberOfLeaves. Its value will be equal to the number of elements in leaves.

You are allowed to transform our tree by performing a sequence of steps. In each step you can select any inner node of the tree and swap its left and right subtrees. (That is, the left child of the selected node becomes its right child and vice versa.) You may do arbitrarily many steps, including zero. You may choose the same node multiple times if you wish.

After you are done transforming the tree, we are going to read the values stored in its leaves (again, from the left to the right). Your task is to make this sequence as small as possible. Compute and return the lexicographically smallest sequence that can be constructed in the leaves of the tree. (See Notes for the definition of "lexicographically smaller".)

Definition

Class:
SwappingNodes
Method:
swapNodes
Parameters:
int[], int
Returns:
int[]
Method signature:
int[] swapNodes(int[] leaves, int numberOfLeaves)
(be sure your method is public)

Notes

  • Given two distinct sequences A = a0,a1,....an-1 and B = b0,b1,....bn-1, the lexicographically smaller sequence is the one that has a smaller value at the first index where they differ. In other words, the sequence A is smaller than the sequence B if for some index x we have (ax < bx) and (for all i < x : ai = bi).

Constraints

  • leaves will have between 1 and 512 elements, inclusive.
  • The number of elements in leaves will be a power of 2.
  • Each element of leaves will be between 1 and 512, inclusive.
  • All values of leaves will be distinct.
  • numberOfLeaves will be equal to the number of elements in leaves.

Examples

  1. {5,2,1,3}

    4

    Returns: {1, 3, 2, 5 }

    The input describes the tree shown in the problem statement. One optimal solution looks as follows: Select node C and swap its subtrees. This produces a tree that corresponds to the sequence {1, 3, 5, 2}. Then, select node A and swap its subtrees. (Note that A is currently the right child of C.) This produces a tree that corresponds to the sequence {1, 3, 2, 5}. The sequence {1, 3, 2, 5} is the lexicographically smallest of all sequences that can be produced by transforming the tree, and therefore this is the correct return value.

  2. {13, 10, 18, 16}

    4

    Returns: {10, 13, 16, 18 }

    Here, one optimal solution looks as follows: Select the left child of the root of the tree. New sequence: {10, 13, 18, 16}. Then, select the right child of the root of the tree. New sequence: {10, 13, 16, 18}. Obviously, the sequence we just produced has to be optimal, so we are done.

  3. {1}

    1

    Returns: {1 }

  4. {16,152,3,59}

    4

    Returns: {3, 59, 16, 152 }

  5. {204,95,359,280,228,64,335,9}

    8

    Returns: {9, 335, 64, 228, 95, 204, 280, 359 }

  6. {43,81,147,49,254,74,299,134,170,414,187,398,16,238,36,422}

    16

    Returns: {16, 238, 36, 422, 170, 414, 187, 398, 43, 81, 49, 147, 74, 254, 134, 299 }

  7. {104,329,422,233,257,247,214,421,466,303,498,53,151,225,52,371,276,262,15,321,312,281,437,512,251,394,81,332,278,66,491,302,370,399,476,173,490,407,283,351,380,509,199,435,91,457,411,239,473,428,12,44,414,187,28,449,482,258,287,359,391,209,309,434}

    64

    Returns: {12, 44, 428, 473, 28, 449, 187, 414, 209, 391, 309, 434, 258, 482, 287, 359, 91, 457, 239, 411, 199, 435, 380, 509, 173, 476, 370, 399, 283, 351, 407, 490, 15, 321, 262, 276, 281, 312, 437, 512, 66, 278, 302, 491, 81, 332, 251, 394, 52, 371, 151, 225, 53, 498, 303, 466, 104, 329, 233, 422, 214, 421, 247, 257 }

  8. {241,441,305,388,259,455,87,335,317,179,167,196,467,58,219,45,486,168,13,356,479,48,433,231,171,283,109,473,322,104,328,325,468,403,351,367,461,383,445,402,348,345,304,111,333,225,447,212,460,405,134,169,145,384,243,28,320,505,391,25,63,437,296,197,336,232,70,154,36,117,399,343,236,353,463,260,298,41,250,20,172,22,55,192,269,107,297,292,302,146,97,156,376,148,120,54,3,265,294,439,21,275,458,251,210,407,67,128,99,306,363,209,88,495,142,78,252,161,321,434,493,233,422,152,216,309,442,340,452,126,17,427,214,27,271,247,415,223,498,228,347,77,457,352,72,314,143,478,1,257,11,35,466,49,65,71,295,425,93,37,62,313,39,185,182,412,42,450,80,204,451,446,284,379,476,360,312,98,230,181,508,354,500,418,318,193,507,315,440,38,470,82,289,485,368,85,472,490,310,203,258,366,428,105,122,103,79,206,497,227,416,51,2,83,100,43,254,323,10,301,501,81,178,264,330,483,413,12,263,488,285,444,150,113,222,291,144,127,34,187,371,94,180,96,424,268,453,73,341,235,386,459,149,16,380,220}

    256

    Returns: {1, 257, 11, 35, 72, 314, 143, 478, 37, 93, 295, 425, 49, 466, 65, 71, 17, 427, 126, 452, 27, 214, 247, 271, 77, 347, 352, 457, 223, 415, 228, 498, 38, 440, 82, 470, 193, 318, 315, 507, 98, 312, 181, 230, 354, 508, 418, 500, 39, 185, 62, 313, 42, 450, 182, 412, 80, 204, 446, 451, 284, 379, 360, 476, 2, 83, 43, 100, 51, 416, 227, 497, 10, 301, 254, 323, 81, 501, 178, 264, 79, 206, 103, 122, 105, 428, 258, 366, 85, 368, 289, 485, 203, 310, 472, 490, 12, 413, 330, 483, 263, 488, 285, 444, 34, 187, 127, 144, 113, 150, 222, 291, 16, 149, 220, 380, 235, 341, 386, 459, 73, 453, 268, 424, 94, 371, 96, 180, 3, 265, 294, 439, 21, 275, 251, 458, 67, 128, 210, 407, 99, 306, 209, 363, 78, 142, 88, 495, 161, 252, 321, 434, 152, 422, 233, 493, 216, 309, 340, 442, 20, 250, 41, 298, 236, 353, 260, 463, 36, 117, 343, 399, 70, 154, 232, 336, 22, 172, 55, 192, 107, 269, 292, 297, 54, 120, 148, 376, 97, 156, 146, 302, 13, 356, 168, 486, 48, 479, 231, 433, 104, 322, 325, 328, 109, 473, 171, 283, 45, 219, 58, 467, 167, 196, 179, 317, 87, 335, 259, 455, 241, 441, 305, 388, 25, 391, 320, 505, 63, 437, 197, 296, 28, 243, 145, 384, 134, 169, 405, 460, 111, 304, 345, 348, 212, 447, 225, 333, 351, 367, 403, 468, 383, 461, 402, 445 }

  9. {464,412,484,48,429,277,305,487,386,133,498,507,1,192,147,287,162,93,397,43,265,180,128,327,8,330,502,144,319,72,351,298,148,254,216,209,57,51,83,119,110,472,223,275,66,189,200,316,219,176,17,490,236,181,108,421,238,259,235,358,172,355,174,388,325,123,419,452,504,276,263,368,306,314,27,91,357,393,408,293,260,239,457,286,41,427,433,167,328,363,59,195,377,224,231,250,462,86,94,103,202,139,331,274,348,221,4,42,353,387,84,299,61,102,164,269,87,118,214,486,151,203,62,28,294,483,448,359,85,402,122,257,20,378,455,470,218,227,179,261,7,141,411,401,138,398,104,373,337,39,273,49,435,225,307,442,322,476,372,347,101,207,211,95,338,410,300,186,204,11,335,56,36,360,81,431,37,136,245,480,450,143,296,443,425,477,157,107,253,199,100,418,512,399,23,436,14,471,460,430,446,146,312,210,414,405,375,131,341,112,262,187,80,74,255,391,389,161,271,76,206,270,366,13,302,301,44,318,352,501,492,67,228,497,467,511,113,447,364,60,403,444,35,500,449,156,264,16,308,432,407,38,150,459,68,481,244,320,488,33,278,246,256,311,247,379,283,2,98,346,404,115,326,284,317,137,5,198,289,451,365,437,479,82,505,135,145,9,482,124,26,456,152,242,485,489,382,159,71,196,25,175,424,465,45,445,163,3,499,354,208,32,394,165,129,288,132,342,491,88,453,54,350,304,183,281,268,478,126,184,34,461,475,127,153,168,349,194,116,333,332,439,155,458,508,90,252,205,134,140,18,40,78,428,282,222,345,297,295,390,417,473,441,182,438,154,173,111,169,191,120,114,19,374,234,310,240,423,416,356,31,434,248,384,415,185,160,503,313,493,290,220,249,63,406,362,69,383,105,170,73,178,79,400,149,466,329,12,292,53,267,117,272,52,420,70,241,188,469,343,381,96,369,495,474,21,380,130,201,251,237,361,77,454,468,75,97,285,426,197,15,212,339,279,266,396,24,336,340,392,334,230,121,58,376,10,171,409,463,46,509,22,303,510,315,243,125,193,64,29,166,215,226,321,422,370,229,324,158,190,6,280,106,55,142,99,47,217,258,89,371,65,344,92,232,413,395,177,440,323,309,494,291,213,109,233,367,50,496,506,385,30}

    512

    Returns: {1, 192, 147, 287, 133, 386, 498, 507, 48, 484, 412, 464, 277, 429, 305, 487, 8, 330, 144, 502, 72, 319, 298, 351, 43, 397, 93, 162, 128, 327, 180, 265, 17, 490, 176, 219, 108, 421, 181, 236, 172, 355, 174, 388, 235, 358, 238, 259, 51, 57, 83, 119, 148, 254, 209, 216, 66, 189, 200, 316, 110, 472, 223, 275, 4, 42, 221, 348, 84, 299, 353, 387, 86, 462, 94, 103, 139, 202, 274, 331, 28, 62, 151, 203, 294, 483, 359, 448, 61, 102, 164, 269, 87, 118, 214, 486, 27, 91, 306, 314, 293, 408, 357, 393, 123, 325, 419, 452, 263, 368, 276, 504, 41, 427, 167, 433, 239, 260, 286, 457, 59, 195, 328, 363, 224, 377, 231, 250, 7, 141, 401, 411, 179, 261, 218, 227, 20, 378, 455, 470, 85, 402, 122, 257, 39, 337, 49, 273, 104, 373, 138, 398, 225, 435, 307, 442, 322, 476, 347, 372, 11, 204, 56, 335, 36, 360, 81, 431, 95, 211, 101, 207, 186, 300, 338, 410, 37, 136, 245, 480, 143, 450, 296, 443, 100, 418, 199, 253, 107, 157, 425, 477, 13, 366, 206, 270, 76, 271, 161, 389, 74, 80, 255, 391, 112, 341, 187, 262, 14, 471, 430, 460, 23, 436, 399, 512, 131, 375, 405, 414, 146, 446, 210, 312, 16, 264, 156, 449, 35, 500, 403, 444, 38, 407, 308, 432, 68, 481, 150, 459, 44, 318, 301, 302, 67, 492, 352, 501, 60, 364, 113, 447, 228, 497, 467, 511, 2, 283, 247, 379, 98, 346, 115, 404, 33, 488, 244, 320, 246, 278, 256, 311, 5, 198, 289, 451, 137, 317, 284, 326, 9, 145, 135, 505, 82, 479, 365, 437, 3, 163, 45, 445, 32, 208, 354, 499, 88, 491, 132, 342, 129, 288, 165, 394, 25, 175, 424, 465, 71, 196, 159, 382, 26, 456, 124, 482, 152, 242, 485, 489, 18, 40, 134, 140, 90, 508, 205, 252, 116, 333, 194, 349, 155, 458, 332, 439, 34, 461, 126, 184, 127, 475, 153, 168, 54, 453, 304, 350, 183, 281, 268, 478, 19, 374, 234, 310, 114, 120, 169, 191, 31, 434, 248, 384, 240, 423, 356, 416, 78, 428, 222, 282, 295, 390, 297, 345, 111, 173, 154, 438, 182, 441, 417, 473, 6, 280, 55, 106, 47, 217, 99, 142, 65, 371, 89, 258, 92, 344, 232, 413, 30, 385, 496, 506, 50, 367, 109, 233, 177, 395, 323, 440, 213, 291, 309, 494, 10, 376, 58, 121, 230, 334, 340, 392, 22, 509, 303, 510, 46, 463, 171, 409, 29, 64, 166, 215, 125, 193, 243, 315, 158, 190, 229, 324, 226, 321, 370, 422, 12, 329, 149, 466, 73, 178, 79, 400, 52, 272, 70, 420, 53, 292, 117, 267, 63, 249, 362, 406, 69, 383, 105, 170, 160, 503, 185, 415, 220, 290, 313, 493, 15, 212, 279, 339, 24, 336, 266, 396, 75, 468, 77, 454, 97, 285, 197, 426, 21, 474, 130, 380, 201, 251, 237, 361, 96, 381, 369, 495, 188, 241, 343, 469 }

  10. {435,343,426,420,99,407,352,353,265,422,457,423,210,10,404,255,97,502,510,288,509,369,310,218,198,82,83,223,188,419,437,251,217,237,388,311,9,295,88,199,219,224,221,14,126,456,128,90,411,134,383,303,453,281,317,489,95,362,347,102,178,205,392,285,104,256,331,23,306,272,496,336,100,386,308,434,187,448,393,94,299,368,286,226,356,222,2,38,268,342,325,458,481,240,397,230,249,364,447,162,171,41,487,81,17,410,39,182,119,494,371,381,3,469,287,391,439,191,124,270,53,427,258,283,387,227,44,46}

    128

    Returns: {2, 38, 222, 356, 226, 286, 299, 368, 230, 397, 240, 481, 268, 342, 325, 458, 23, 331, 104, 256, 272, 306, 336, 496, 94, 393, 187, 448, 100, 386, 308, 434, 3, 469, 287, 391, 124, 270, 191, 439, 44, 46, 227, 387, 53, 427, 258, 283, 17, 410, 39, 182, 119, 494, 371, 381, 41, 171, 81, 487, 162, 447, 249, 364, 9, 295, 88, 199, 217, 237, 311, 388, 14, 221, 219, 224, 90, 128, 126, 456, 95, 362, 102, 347, 178, 205, 285, 392, 134, 411, 303, 383, 281, 453, 317, 489, 10, 210, 255, 404, 265, 422, 423, 457, 99, 407, 352, 353, 343, 435, 420, 426, 82, 198, 83, 223, 188, 419, 251, 437, 97, 502, 288, 510, 218, 310, 369, 509 }

  11. {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,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512}

    512

    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, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512 }

  12. {512,511,510,509,508,507,506,505,504,503,502,501,500,499,498,497,496,495,494,493,492,491,490,489,488,487,486,485,484,483,482,481,480,479,478,477,476,475,474,473,472,471,470,469,468,467,466,465,464,463,462,461,460,459,458,457,456,455,454,453,452,451,450,449,448,447,446,445,444,443,442,441,440,439,438,437,436,435,434,433,432,431,430,429,428,427,426,425,424,423,422,421,420,419,418,417,416,415,414,413,412,411,410,409,408,407,406,405,404,403,402,401,400,399,398,397,396,395,394,393,392,391,390,389,388,387,386,385,384,383,382,381,380,379,378,377,376,375,374,373,372,371,370,369,368,367,366,365,364,363,362,361,360,359,358,357,356,355,354,353,352,351,350,349,348,347,346,345,344,343,342,341,340,339,338,337,336,335,334,333,332,331,330,329,328,327,326,325,324,323,322,321,320,319,318,317,316,315,314,313,312,311,310,309,308,307,306,305,304,303,302,301,300,299,298,297,296,295,294,293,292,291,290,289,288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,272,271,270,269,268,267,266,265,264,263,262,261,260,259,258,257,256,255,254,253,252,251,250,249,248,247,246,245,244,243,242,241,240,239,238,237,236,235,234,233,232,231,230,229,228,227,226,225,224,223,222,221,220,219,218,217,216,215,214,213,212,211,210,209,208,207,206,205,204,203,202,201,200,199,198,197,196,195,194,193,192,191,190,189,188,187,186,185,184,183,182,181,180,179,178,177,176,175,174,173,172,171,170,169,168,167,166,165,164,163,162,161,160,159,158,157,156,155,154,153,152,151,150,149,148,147,146,145,144,143,142,141,140,139,138,137,136,135,134,133,132,131,130,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,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}

    512

    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, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512 }

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

    8

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

  14. {5, 2, 1, 3 }

    4

    Returns: {1, 3, 2, 5 }

  15. {2, 5, 6, 7, 1, 3, 99, 100 }

    8

    Returns: {1, 3, 99, 100, 2, 5, 6, 7 }

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

    8

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

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

    8

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

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

    8

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

  19. {206, 310, 343, 280, 461, 349, 367, 153, 271, 322, 321, 125, 245, 491, 395, 151, 247, 328, 391, 463, 176, 272, 430, 316, 375, 8, 376, 473, 139, 100, 403, 270, 301, 156, 447, 40, 505, 4, 152, 102, 470, 484, 472, 373, 302, 161, 507, 320, 180, 181, 199, 347, 314, 284, 198, 508, 476, 197, 240, 45, 317, 318, 47, 104, 296, 96, 443, 201, 171, 382, 71, 150, 164, 149, 252, 293, 385, 190, 460, 43, 192, 53, 73, 54, 273, 402, 246, 208, 145, 147, 464, 434, 485, 478, 154, 435, 117, 334, 278, 465, 291, 17, 324, 410, 432, 362, 433, 276, 179, 222, 230, 11, 495, 350, 372, 59, 1, 307, 359, 35, 303, 424, 363, 496, 135, 356, 177, 119, 49, 2, 211, 7, 188, 120, 244, 415, 233, 167, 268, 237, 448, 74, 429, 353, 215, 213, 70, 426, 80, 466, 52, 88, 217, 136, 504, 418, 250, 401, 36, 183, 108, 512, 127, 32, 368, 255, 386, 234, 19, 202, 482, 9, 309, 83, 281, 114, 477, 436, 42, 105, 60, 483, 311, 146, 90, 488, 277, 143, 87, 275, 30, 31, 170, 326, 224, 500, 439, 422, 76, 489, 239, 55, 144, 196, 132, 131, 229, 140, 122, 342, 13, 162, 503, 58, 75, 191, 251, 445, 274, 313, 346, 427, 205, 419, 449, 344, 99, 186, 209, 411, 242, 509, 28, 370, 219, 440, 330, 97, 405, 490, 369, 12, 116, 497, 454, 479, 408, 37, 444, 118, 226, 498, 332, 457, 438, 283, 417, 374, 184, 159, 502, 241, 169, 442, 182, 469, 174, 6, 380, 467, 412, 48, 264, 210, 335, 56, 111, 50, 279, 227, 397, 81, 354, 225, 358, 115, 85, 499, 421, 462, 89, 510, 355, 285, 384, 416, 25, 287, 333, 481, 409, 297, 381, 130, 65, 414, 336, 258, 160, 455, 232, 155, 200, 453, 456, 67, 378, 299, 400, 20, 194, 103, 295, 398, 165, 312, 392, 109, 341, 393, 383, 492, 366, 286, 325, 61, 166, 41, 394, 228, 95, 110, 163, 267, 390, 338, 34, 94, 306, 396, 77, 487, 218, 253, 187, 379, 361, 5, 235, 14, 428, 371, 243, 107, 92, 475, 340, 399, 304, 204, 203, 178, 345, 98, 66, 223, 18, 84, 29, 46, 51, 266, 413, 93, 437, 134, 254, 148, 129, 168, 329, 137, 44, 425, 72, 106, 38, 91, 3, 323, 319, 216, 257, 112, 441, 138, 404, 365, 193, 128, 249, 189, 474, 327, 389, 298, 78, 486, 248, 493, 315, 79, 331, 142, 21, 458, 300, 451, 387, 305, 63, 256, 288, 265, 459, 64, 212, 431, 141, 231, 23, 68, 214, 158, 480, 450, 57, 452, 292, 185, 423, 406, 22, 33, 262, 27, 364, 407, 282, 101, 468, 501, 377, 269, 294, 446, 82, 238, 24, 62, 173, 471, 351, 172, 39, 121, 506, 388, 261, 357, 494, 175, 289, 420, 348, 260, 236, 123, 221, 195, 220, 339, 69, 124, 290, 157, 337, 207, 86, 113, 360, 133, 126, 263, 26, 10, 308, 16, 511, 259, 15, 352 }

    512

    Returns: {1, 307, 35, 359, 59, 372, 350, 495, 119, 177, 135, 356, 303, 424, 363, 496, 11, 230, 179, 222, 276, 433, 362, 432, 17, 291, 324, 410, 117, 334, 278, 465, 43, 460, 190, 385, 149, 164, 252, 293, 71, 150, 171, 382, 96, 296, 201, 443, 53, 192, 54, 73, 208, 246, 273, 402, 145, 147, 434, 464, 154, 435, 478, 485, 4, 505, 102, 152, 40, 447, 156, 301, 161, 302, 320, 507, 373, 472, 470, 484, 45, 240, 197, 476, 47, 104, 317, 318, 180, 181, 199, 347, 198, 508, 284, 314, 8, 375, 376, 473, 100, 139, 270, 403, 176, 272, 316, 430, 247, 328, 391, 463, 125, 321, 271, 322, 151, 395, 245, 491, 153, 367, 349, 461, 206, 310, 280, 343, 2, 49, 7, 211, 120, 188, 244, 415, 74, 448, 353, 429, 167, 233, 237, 268, 36, 183, 250, 401, 136, 217, 418, 504, 52, 88, 80, 466, 70, 426, 213, 215, 9, 482, 19, 202, 83, 309, 114, 281, 32, 127, 108, 512, 234, 386, 255, 368, 30, 31, 87, 275, 90, 488, 143, 277, 42, 105, 436, 477, 60, 483, 146, 311, 12, 369, 116, 497, 37, 408, 454, 479, 118, 444, 226, 498, 283, 438, 332, 457, 28, 370, 219, 440, 97, 330, 405, 490, 99, 186, 344, 449, 209, 411, 242, 509, 13, 162, 122, 342, 58, 503, 75, 191, 205, 419, 346, 427, 251, 445, 274, 313, 55, 239, 144, 196, 131, 132, 140, 229, 76, 489, 422, 439, 170, 326, 224, 500, 3, 323, 38, 91, 44, 425, 72, 106, 129, 168, 137, 329, 134, 437, 148, 254, 112, 257, 216, 319, 138, 441, 365, 404, 128, 193, 189, 249, 298, 389, 327, 474, 21, 458, 300, 451, 63, 256, 305, 387, 78, 486, 248, 493, 79, 315, 142, 331, 23, 68, 158, 214, 57, 452, 450, 480, 64, 459, 265, 288, 141, 231, 212, 431, 10, 26, 16, 308, 15, 352, 259, 511, 86, 113, 207, 337, 126, 263, 133, 360, 69, 124, 157, 290, 195, 221, 220, 339, 123, 236, 260, 348, 175, 494, 289, 420, 22, 33, 27, 262, 185, 292, 406, 423, 101, 282, 364, 407, 269, 377, 468, 501, 24, 62, 173, 471, 82, 238, 294, 446, 39, 121, 172, 351, 261, 357, 388, 506, 5, 361, 14, 235, 187, 379, 218, 253, 92, 475, 340, 399, 107, 243, 371, 428, 18, 84, 29, 46, 51, 266, 93, 413, 66, 223, 98, 345, 178, 203, 204, 304, 34, 94, 338, 390, 77, 487, 306, 396, 41, 166, 228, 394, 95, 110, 163, 267, 61, 325, 286, 366, 341, 393, 383, 492, 103, 194, 295, 398, 109, 392, 165, 312, 6, 174, 182, 469, 48, 412, 380, 467, 159, 184, 374, 417, 169, 442, 241, 502, 50, 111, 227, 279, 56, 335, 210, 264, 81, 397, 225, 354, 85, 499, 115, 358, 20, 400, 299, 378, 67, 456, 200, 453, 65, 414, 258, 336, 155, 232, 160, 455, 25, 287, 333, 481, 130, 381, 297, 409, 89, 510, 421, 462, 285, 355, 384, 416 }

  20. {479, 80, 143, 276, 404, 191, 226, 65, 300, 140, 107, 245, 472, 345, 256, 66, 33, 28, 393, 94, 512, 40, 239, 433, 299, 275, 281, 212, 106, 95, 56, 205, 123, 44, 9, 510, 164, 86, 301, 391, 210, 35, 233, 109, 92, 193, 75, 314, 202, 456, 449, 257, 503, 186, 70, 410, 137, 282, 408, 303, 51, 509, 506, 246, 128, 397, 412, 2, 201, 260, 244, 439, 423, 291, 316, 64, 319, 217, 54, 149, 475, 264, 18, 323, 206, 220, 496, 377, 371, 141, 307, 405, 455, 293, 110, 148, 192, 468, 100, 459, 278, 470, 372, 195, 406, 485, 488, 378, 450, 374, 288, 223, 117, 399, 25, 357, 121, 170, 1, 253, 116, 351, 7, 203, 152, 356, 353, 487, 492, 483, 469, 484, 490, 98, 71, 359, 454, 388, 167, 444, 289, 31, 428, 421, 360, 250, 82, 296, 112, 398, 308, 88, 11, 379, 172, 76, 368, 305, 263, 478, 364, 365, 113, 396, 200, 211, 467, 332, 495, 78, 267, 380, 292, 174, 68, 151, 240, 219, 453, 481, 162, 418, 156, 333, 160, 104, 367, 437, 27, 430, 184, 295, 294, 17, 133, 188, 458, 502, 139, 261, 125, 111, 145, 373, 130, 411, 171, 36, 473, 236, 47, 381, 228, 270, 26, 464, 344, 313, 358, 132, 457, 286, 443, 131, 340, 85, 39, 38, 341, 326, 431, 283, 45, 354, 386, 37, 197, 248, 155, 20, 452, 409, 13, 402, 96, 436, 362, 16, 425, 62, 242, 259, 498, 194, 366, 389, 12, 476, 252, 482, 321, 310, 334, 347, 185, 325, 59, 504, 273, 101, 216, 330, 489, 43, 46, 342, 204, 15, 451, 61, 84, 237, 154, 383, 103, 89, 231, 34, 10, 247, 348, 73, 249, 343, 254, 369, 435, 480, 284, 277, 414, 416, 77, 58, 486, 221, 4, 79, 390, 311, 127, 461, 163, 72, 385, 511, 234, 493, 119, 417, 55, 266, 432, 81, 327, 108, 269, 442, 304, 97, 138, 403, 274, 335, 280, 394, 169, 120, 225, 338, 105, 422, 224, 30, 90, 285, 395, 337, 238, 474, 440, 312, 376, 407, 83, 67, 99, 287, 22, 329, 424, 375, 382, 176, 346, 144, 190, 135, 124, 415, 74, 315, 298, 161, 441, 115, 57, 500, 429, 392, 350, 134, 41, 165, 306, 320, 426, 445, 175, 118, 218, 427, 317, 255, 178, 42, 471, 114, 446, 8, 349, 142, 434, 180, 232, 209, 413, 52, 50, 213, 182, 5, 309, 181, 370, 198, 384, 196, 322, 336, 173, 241, 447, 179, 166, 463, 268, 271, 318, 229, 339, 24, 168, 32, 477, 6, 207, 23, 177, 87, 146, 499, 355, 438, 63, 199, 387, 122, 91, 183, 49, 420, 243, 159, 400, 214, 363, 19, 290, 491, 272, 21, 497, 297, 158, 361, 157, 102, 187, 302, 215, 505, 419, 448, 508, 3, 328, 189, 352, 265, 258, 466, 208, 48, 462, 262, 29, 93, 53, 465, 401, 150, 235, 460, 153, 331, 69, 14, 501, 60, 494, 279, 230, 147, 136, 324, 129, 227, 222, 251, 507, 126 }

    512

    Returns: {1, 253, 121, 170, 25, 357, 117, 399, 7, 203, 116, 351, 152, 356, 353, 487, 100, 459, 192, 468, 195, 372, 278, 470, 223, 288, 374, 450, 378, 488, 406, 485, 2, 412, 128, 397, 201, 260, 244, 439, 54, 149, 217, 319, 64, 316, 291, 423, 18, 323, 264, 475, 206, 220, 377, 496, 110, 148, 293, 455, 141, 371, 307, 405, 9, 510, 44, 123, 86, 164, 301, 391, 35, 210, 109, 233, 75, 314, 92, 193, 51, 509, 246, 506, 137, 282, 303, 408, 70, 410, 186, 503, 202, 456, 257, 449, 28, 33, 94, 393, 40, 512, 239, 433, 56, 205, 95, 106, 212, 281, 275, 299, 65, 226, 191, 404, 80, 479, 143, 276, 66, 256, 345, 472, 107, 245, 140, 300, 11, 379, 76, 172, 263, 478, 305, 368, 82, 296, 250, 360, 88, 308, 112, 398, 31, 289, 421, 428, 167, 444, 388, 454, 71, 359, 98, 490, 469, 484, 483, 492, 27, 430, 184, 295, 104, 160, 367, 437, 156, 333, 162, 418, 219, 240, 453, 481, 68, 151, 174, 292, 78, 495, 267, 380, 113, 396, 364, 365, 200, 211, 332, 467, 13, 402, 409, 452, 16, 362, 96, 436, 62, 425, 242, 259, 194, 498, 366, 389, 20, 155, 197, 248, 37, 386, 45, 354, 38, 39, 85, 340, 283, 431, 326, 341, 17, 294, 133, 188, 139, 261, 458, 502, 36, 171, 130, 411, 111, 125, 145, 373, 26, 464, 228, 270, 47, 381, 236, 473, 131, 443, 286, 457, 132, 358, 313, 344, 3, 508, 419, 448, 189, 328, 265, 352, 102, 157, 158, 361, 187, 302, 215, 505, 19, 363, 290, 491, 21, 272, 297, 497, 49, 420, 91, 183, 159, 243, 214, 400, 14, 69, 60, 501, 147, 230, 279, 494, 126, 507, 222, 251, 129, 227, 136, 324, 29, 93, 262, 462, 48, 208, 258, 466, 53, 465, 150, 401, 153, 331, 235, 460, 5, 182, 50, 213, 181, 309, 198, 370, 52, 413, 209, 232, 142, 349, 180, 434, 8, 446, 114, 471, 42, 178, 255, 317, 118, 175, 218, 427, 306, 320, 426, 445, 6, 477, 32, 168, 23, 207, 87, 177, 63, 199, 122, 387, 146, 499, 355, 438, 24, 339, 229, 318, 166, 463, 268, 271, 173, 241, 179, 447, 196, 384, 322, 336, 4, 79, 221, 486, 127, 461, 311, 390, 72, 163, 385, 511, 119, 417, 234, 493, 10, 247, 73, 348, 249, 343, 254, 369, 58, 77, 414, 416, 277, 284, 435, 480, 12, 476, 252, 482, 310, 321, 334, 347, 59, 504, 185, 325, 101, 273, 216, 330, 15, 204, 61, 451, 43, 489, 46, 342, 34, 231, 89, 103, 84, 237, 154, 383, 22, 329, 99, 287, 67, 83, 376, 407, 135, 190, 144, 346, 176, 382, 375, 424, 41, 165, 134, 350, 57, 500, 392, 429, 74, 315, 124, 415, 115, 441, 161, 298, 30, 224, 105, 422, 120, 169, 225, 338, 90, 285, 337, 395, 238, 474, 312, 440, 55, 266, 81, 432, 108, 327, 269, 442, 97, 304, 138, 403, 274, 335, 280, 394 }

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

    8

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

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

    8

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

  23. {28, 17, 8, 25, 7, 77, 31, 33 }

    8

    Returns: {7, 77, 31, 33, 8, 25, 17, 28 }

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

    8

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

  25. {2, 5, 6, 7, 99, 100, 1, 3 }

    8

    Returns: {1, 3, 99, 100, 2, 5, 6, 7 }

  26. {1 }

    1

    Returns: {1 }

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

    8

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

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

    8

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

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

    8

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

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

    8

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

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

    8

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

  32. {13, 10, 18, 16, 1, 3, 20, 21, 6, 7, 19, 28, 9, 8, 2, 5 }

    16

    Returns: {1, 3, 20, 21, 10, 13, 16, 18, 2, 5, 8, 9, 6, 7, 19, 28 }

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

    8

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

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

    8

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

  35. {1, 2, 6, 7, 3, 4, 16, 17 }

    8

    Returns: {1, 2, 6, 7, 3, 4, 16, 17 }

  36. {1, 3, 2, 5 }

    4

    Returns: {1, 3, 2, 5 }

  37. {5, 6, 7, 8, 3, 4, 10, 11 }

    8

    Returns: {3, 4, 10, 11, 5, 6, 7, 8 }

  38. {1, 4, 2, 3 }

    4

    Returns: {1, 4, 2, 3 }

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

    8

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

  40. {2, 3, 4, 5, 10, 30, 40, 50 }

    8

    Returns: {2, 3, 4, 5, 10, 30, 40, 50 }

  41. {1, 300, 400, 500, 10, 30, 40, 50 }

    8

    Returns: {1, 300, 400, 500, 10, 30, 40, 50 }

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

    8

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

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: