Statistics

Problem Statement for "PointsOnAxis"

Problem Statement

There are several distinct points located on the non-negative side of the x-axis. One of those points is at the origin (at 0). For each unique pair of points we write down the distance between them. Note that pairs (a, b) and pairs (b, a) are not unique pairs.

Given a int[] of those distances, return a int[] containing the locations of all points arranged in ascending order. If more than one set of locations is possible then return the set (represented as a int[]) which is lexicographically earliest (see example 1). A int[], n, comes before a int[], m, lexicographically if and only if, for the first element in which they differ, the element of n is smaller. If no set of locations is possible then return an empty int[].

For example: distances = {5, 2, 1, 6, 2, 3, 3, 4, 5, 6, 3, 9, 1, 4, 1}. This in order is {1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 9}. The only possible arrangement of points is the following:

  0    1    2    3    4    5    6    7    8    9
--x----|----|----x----x----x----x----|----|----x--

Here 'x' represents a point. Thus the method should return {0, 3, 4, 5, 6, 9}

Definition

Class:
PointsOnAxis
Method:
findPoints
Parameters:
int[]
Returns:
int[]
Method signature:
int[] findPoints(int[] distances)
(be sure your method is public)

Notes

  • There cannot be more than one point at the same location, because elements in distances are never 0.

Constraints

  • the number of elements in distances will be N(N-1)/2, where N is the number of points.
  • N will be between 2 and 10 inclusive.
  • each element in distances will be between 1 and 1000000 inclusive.

Examples

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

    Returns: { 0, 3, 4, 5, 6, 9 }

    See above.

  2. {20,100,120}

    Returns: { 0, 20, 120 }

    The possible sets of locations are {0,100,120} and {0,20,120}. Since 20 comes before 100, the method should return {0,20,120}.

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

    Returns: { 0, 2, 3, 7 }

  4. {1,2,4}

    Returns: { }

    There are no possible sets of locations.

  5. {237601, 843904, 56786, 429289, 52254, 83576, 220417, 606303, 180815, 191688, 185347, 154025, 17184, 787118, 414615, 791650, 760328, 623487, 372503, 4532, 26790, 163631, 377035, 345713, 208872, 31322, 168163, 136841}

    Returns: { 0, 52254, 56786, 83576, 220417, 237601, 429289, 843904 }

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

    Returns: { 0, 1, 2, 5, 6, 7 }

  7. {2, 5, 6, 8, 11, 16, 17, 19, 22, 24, 29, 31, 37, 48, 53}

    Returns: { 0, 5, 16, 22, 24, 53 }

  8. {70, 17, 13, 53, 83, 30}

    Returns: { 0, 13, 30, 83 }

  9. {8, 61, 7, 4, 69, 15, 4, 54, 65, 11}

    Returns: { 0, 4, 8, 15, 69 }

  10. {77, 52, 89, 3, 31, 32, 81, 55, 25, 12, 80, 46, 45, 4, 22, 37, 55, 21, 20, 29, 3, 92, 58, 57, 8, 34, 34, 35, 84, 58, 1, 50, 24, 49, 23, 26}

    Returns: { 0, 3, 34, 35, 55, 58, 80, 84, 92 }

  11. {37, 29, 54, 25, 18, 19, 46, 8, 17, 12, 19, 56, 9, 25, 4, 11, 48, 17, 29, 36, 73, 8, 7, 44, 21, 37, 28, 65}

    Returns: { 0, 8, 17, 25, 29, 36, 54, 73 }

  12. {26, 8, 55, 22, 27, 50, 34, 29, 4, 1, 24, 63, 30, 35, 58, 33, 28, 5, 5, 28, 23}

    Returns: { 0, 5, 28, 29, 33, 55, 63 }

  13. {20, 2, 43, 67, 19, 49, 72, 24, 19, 22, 23, 47, 39, 29, 52, 44, 1, 45, 69, 17, 51, 74, 22, 21, 24, 62, 6, 29, 67, 24, 86, 18, 5, 91, 48, 68, 91, 5, 38, 23, 73, 30, 96, 53, 43}

    Returns: { 0, 5, 22, 24, 43, 44, 67, 73, 91, 96 }

  14. {24, 49, 31, 44, 23, 25, 26, 27, 4, 73, 7, 68, 47, 1, 2, 3, 20, 80, 5, 26, 74, 75, 76, 53, 75, 54, 6, 5, 4, 27, 21, 69, 70, 71, 48, 48, 49, 50, 27, 1, 2, 21, 1, 22, 23}

    Returns: { 0, 4, 5, 6, 7, 27, 31, 54, 75, 80 }

  15. {44}

    Returns: { 0, 44 }

  16. {10, 68, 60, 58, 50, 8}

    Returns: { 0, 8, 58, 68 }

  17. {56, 30, 77, 1, 26, 21, 57, 47, 31, 78}

    Returns: { 0, 1, 31, 57, 78 }

  18. {176630, 227598, 568688, 102567, 2763, 85886, 236904, 89171, 205038, 404228, 392058, 74063, 179393, 90744, 413534, 87459, 28408, 796286, 330165, 224835, 313484, 9306, 316769, 432636, 466121, 571451, 482802, 805592, 479517, 363650, 105330, 16681, 339471, 13396, 102471, 88649, 234141, 91934, 207801, 322790, 3285, 119152, 326075, 441942, 115867}

    Returns: { 0, 9306, 234141, 236904, 322790, 326075, 339471, 413534, 441942, 805592 }

  19. {170945, 389149, 722857, 100263, 47332, 248636, 171128, 560094, 893802, 70682, 123613, 419581, 183, 333708, 489412, 436481, 140513, 560277, 823120, 770189, 474221, 893985, 52931, 348899, 70865, 295968, 123796, 419764}

    Returns: { 0, 183, 70865, 123796, 171128, 419764, 560277, 893985 }

  20. {14740, 99980, 114720}

    Returns: { 0, 14740, 114720 }

  21. {589785}

    Returns: { 0, 589785 }

  22. {551951, 147069, 435595, 521734, 120698, 79258, 474941, 327914, 693186, 699020, 116356, 30217, 672649, 631209, 77010, 224037, 141235, 582664, 668803, 26371, 67811, 622010, 474983, 840255, 86139, 556293, 514853, 39346, 107681, 257591, 642432, 600992, 46793, 193820, 171452, 41440, 595639, 448612, 813884, 554199, 407172, 772444, 147027, 218245, 365272}

    Returns: { 0, 26371, 67811, 147069, 474983, 582664, 622010, 668803, 699020, 840255 }

  23. {534705, 192239, 146428, 200999, 40516, 342466, 681133, 333706, 575221, 338667, 8760, 232755, 347427, 105912, 241515}

    Returns: { 0, 105912, 146428, 338667, 347427, 681133 }

  24. {136673, 332659, 278737, 555779, 57285, 469332, 142064, 692452, 193958, 611396, 223120, 275374, 834516, 336022, 498494}

    Returns: { 0, 142064, 278737, 336022, 611396, 834516 }

  25. {69012, 179002, 20122, 218912, 315126, 73305, 44623, 248014, 89134, 287924, 246114, 142317, 24389, 158880, 39910, 494128, 105697, 223625, 198790, 335248, 53183, 64745, 534038, 145607, 263535, 388431, 270503, 117928}

    Returns: { 0, 39910, 145607, 198790, 218912, 263535, 287924, 534038 }

  26. {791212, 484920, 588670, 32633, 288780, 794939, 306292, 202542, 758579, 502432, 3727, 103750, 452287, 196140, 310019, 556037, 299890, 206269, 256147, 762306, 506159}

    Returns: { 0, 3727, 206269, 310019, 506159, 762306, 794939 }

  27. {704314, 33448, 703076, 336394, 396693, 503890, 737762, 1238, 367920, 307621, 200424, 36524, 369842, 430141, 537338, 366682, 306383, 199186, 60299, 167496, 107197}

    Returns: { }

  28. {247676, 338928, 277873, 411367, 226218, 586604, 525549, 163691, 473894, 61055, 750295, 112710, 689240, 51655, 637585}

    Returns: { 0, 61055, 112710, 338928, 586604, 750295 }

  29. {59376, 662081, 165724, 752637, 96670, 210658, 721457, 106348, 812013, 37294, 270034, 827805, 90556, 758751, 451423, 918361, 69054, 376382, 849307, 541979, 307328}

    Returns: { 0, 69054, 106348, 165724, 376382, 827805, 918361 }

  30. {183471, 8653, 109371, 795194, 498682, 740286, 487375, 538436, 284179, 98904, 633117, 20267, 800104, 7407, 238222, 832452, 464228, 552630, 703755, 154240, 746573, 343967, 548639, 373115, 167682, 89316, 7550, 661669, 347833, 932590, 164514, 192019, 110150, 441710, 664702, 279539}

    Returns: { }

  31. {164141, 521691, 647297, 593899, 814493, 823875, 708676, 981016, 388607, 568217, 585573, 315262, 308129, 248151, 158684, 437366, 344037, 205699, 290242, 462504, 505214, 372265, 230637, 98176, 363933, 363558, 752962, 913504, 927889, 144953, 559240, 604911, 856923, 273711, 956141, 483793, 292269, 545687, 533394, 123708, 817175, 726752, 594667, 347795, 99938}

    Returns: { }

  32. {521507, 106488, 763760, 37215, 639514, 804342, 397562, 841221, 596336, 787410, 937624, 667535, 998283, 88707, 18599, 742664, 852874, 77210, 714390, 349581, 836958, 189821, 903093, 598636, 469675, 60635, 461242, 264983}

    Returns: { }

  33. {959712, 247034, 682280}

    Returns: { }

  34. {245991, 99858, 307577, 422028, 507187, 798877}

    Returns: { }

  35. {157422, 765168, 911073, 540611, 922355, 847304, 765088, 86212, 133068, 540454, 781670, 298671, 995797, 504533, 531162}

    Returns: { }

  36. {474455, 652385, 706361, 208212, 997481, 591835, 600479, 457014, 191318, 162256, 189992, 623587, 209278, 149911, 698243}

    Returns: { }

  37. {847058, 392081, 928200, 158247, 34753, 85882, 160725, 453470, 352093, 571568, 888573, 435409, 720359, 235304, 982312, 76727, 945720, 213927, 602930, 688604, 330797, 395920, 504030, 446748, 178353, 946039, 826133, 416639}

    Returns: { }

  38. {263779, 860582, 560441, 5205, 554849, 657758, 631676, 619984, 919522, 286499, 404023, 267143, 167625, 903904, 745510, 170167, 975065, 227529, 348913, 801591, 533212, 336476, 298772, 177455, 938227, 406658, 254217, 278821, 238320, 848310, 595781, 486881, 675112, 721009, 143156, 590998}

    Returns: { }

  39. {885369, 44825, 532929, 970700, 900987, 617133, 916829, 310662, 19442, 686098, 626135, 117506, 548652, 857008, 852100, 137004, 800776, 187190, 854199, 914235, 220118, 233772, 935122, 341933, 414816, 692897, 621694, 1471, 558169, 122838, 463378, 348015, 524865, 181965, 900034, 495509}

    Returns: { }

  40. {340931, 727061, 200942, 743308, 239066, 360876, 941807, 781132, 748036, 151230, 475593, 187111, 359036, 859256, 382875, 396470, 781739, 503388, 204080, 729200, 467362, 525567, 790991, 13642, 658870, 782122, 111664, 364244}

    Returns: { }

  41. {420585, 99803, 985068, 813107, 297027, 480406, 600100, 443834, 805930, 104581, 759969, 69194, 488191, 962875, 357022, 103270, 259948, 846708, 256252, 940288, 609354}

    Returns: { }

  42. {111240, 971185, 732277, 663657, 792735, 324156, 805826, 766809, 805841, 437469, 228983, 458486, 467109, 577436, 808789}

    Returns: { }

  43. {691486, 435430, 525369, 371805, 947147, 695252, 188790, 651976, 515216, 998246, 904282, 108862, 547274, 48625, 811020, 720070, 46629, 613712, 188730, 81523, 362372, 368821, 742486, 578282, 123688, 22150, 127456, 30227, 661325, 722889, 253190, 796750, 706298, 287985, 290806, 122478}

    Returns: { }

  44. {716441, 615813, 761547, 111220, 555374, 754626, 960050, 753827, 548374, 686258, 93342, 707802, 639147, 723927, 266161, 869825, 962071, 229266, 737318, 475817, 455981, 514763, 614510, 974734, 202160, 795782, 671203, 201944, 175069, 63523, 482382, 345154, 118722, 813778, 241021, 24928}

    Returns: { }

  45. {10,10,10}

    Returns: { }

  46. {30,30,20,20,10,10}

    Returns: { }

  47. {1,2,999998,999999,1000000,1,999997,999998,999999,999996,999997,999998,1,2,1}

    Returns: { 0, 1, 2, 999998, 999999, 1000000 }

  48. {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 11, 12, 12, 13, 14, 15, 17}

    Returns: { 0, 2, 7, 8, 9, 10, 12, 13, 14, 17 }

  49. {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 12, 13, 14, 15, 16}

    Returns: { 0, 1, 6, 7, 9, 10, 11, 12, 14, 16 }

  50. { 1, 6, 10, 23, 26, 34, 41, 53, 55, 5, 9, 22, 25, 33, 40, 52, 54, 4, 17, 20, 28, 35, 47, 49, 13, 16, 24, 31, 43, 45, 3, 11, 18, 30, 32, 8, 15, 27, 29, 7, 19, 21, 12, 14, 3 }

    Returns: { }

  51. { 2, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 11, 11, 12, 13, 13, 14, 15, 15, 16, 17, 18, 18, 20, 20, 21, 22, 24, 25, 25, 26, 27, 30, 30, 31, 33, 35, 35, 38, 39, 42, 44, 46, 5 }

    Returns: { }

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: