Statistics

Problem Statement for "TriangleConstruction"

Problem Statement

The perimeter of a triangle with edge lengths a, b and c is a + b + c.

You have several sticks of various lengths. The int[] lengths contains the length of each stick. Return the maximum possible perimeter of a triangle that can be constructed with your sticks. Each edge of the triangle must be constructed using exactly one stick. You are not allowed to break sticks into smaller pieces. Return -1 if no triangle can be constructed.

Definition

Class:
TriangleConstruction
Method:
greatestPerimeter
Parameters:
int[]
Returns:
int
Method signature:
int greatestPerimeter(int[] lengths)
(be sure your method is public)

Notes

  • You can construct a triangle with edge lengths x <= y <= z if and only if x + y > z.

Constraints

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

Examples

  1. {1,2,2}

    Returns: 5

    In this case there is only one possible triangle, and its perimeter is 1+2+2=5.

  2. {2,3,2,3,2,4}

    Returns: 10

  3. {1,2,3}

    Returns: -1

    No triangle can be constructed from these sticks.

  4. {4, 5, 6, 7, 20}

    Returns: 18

  5. {1000,1000,1000}

    Returns: 3000

  6. {599, 950, 692}

    Returns: 2241

  7. {533, 270, 584, 549}

    Returns: 1666

  8. {431, 653, 859, 63, 576}

    Returns: 2088

  9. {146, 3, 413, 124, 339, 384}

    Returns: 1136

  10. {98, 661, 221, 897, 811, 198, 323}

    Returns: 2369

  11. {214, 108, 273, 467, 991, 434, 767, 659}

    Returns: 2417

  12. {215, 968, 124, 73, 839, 485, 315, 911, 272}

    Returns: 2718

  13. {651, 942, 237, 153, 203, 274, 441, 369, 171, 970}

    Returns: 2563

  14. {369, 625, 49, 219, 161, 89, 385, 903, 448, 949, 906}

    Returns: 2758

  15. {465, 653, 796, 623, 451, 463, 709, 170, 223, 546, 191, 411}

    Returns: 2158

  16. {281, 989, 371, 286, 501, 184, 600, 418, 810, 994, 571, 885, 850}

    Returns: 2868

  17. {17, 384, 661, 429, 315, 833, 529, 209, 897, 226, 350, 824, 684, 199}

    Returns: 2554

  18. {198, 142, 935, 755, 619, 510, 988, 494, 274, 224, 986, 801, 74, 264, 148}

    Returns: 2909

  19. {569, 379, 918, 653, 790, 427, 118, 328, 335, 715, 220, 924, 300, 193, 494, 988}

    Returns: 2830

  20. {400, 639, 445, 28, 537, 976, 392, 959, 869, 755, 831, 374, 634, 56, 50, 147, 809}

    Returns: 2804

  21. {23, 404, 827, 144, 856, 639, 690, 252, 861, 109, 913, 728, 571, 920, 490, 660, 991, 991}

    Returns: 2902

  22. {116, 372, 150, 493, 338, 995, 61, 935, 205, 117, 271, 770, 490, 670, 445, 895, 126, 722, 959}

    Returns: 2889

  23. {53, 846, 90, 873, 185, 364, 592, 817, 115, 723, 839, 92, 312, 267, 697, 176, 136, 816, 438, 492}

    Returns: 2558

  24. {116, 373, 471, 540, 350, 318, 804, 561, 428, 915, 64, 853, 498, 600, 439, 732, 139, 497, 512, 510, 796}

    Returns: 2572

  25. {99, 789, 673, 53, 518, 28, 523, 452, 902, 818, 244, 664, 769, 987, 226, 168, 931, 112, 759, 510, 413, 573}

    Returns: 2820

  26. {205, 867, 404, 454, 354, 15, 373, 381, 454, 781, 182, 219, 681, 81, 776, 721, 250, 311, 393, 353, 498, 986, 13}

    Returns: 2634

  27. {854, 646, 429, 917, 900, 235, 601, 48, 942, 84, 988, 525, 682, 304, 674, 203, 203, 807, 499, 703, 19, 738, 265, 781}

    Returns: 2847

  28. {395, 370, 683, 98, 968, 968, 179, 806, 644, 204, 657, 919, 998, 657, 762, 16, 574, 230, 89, 144, 194, 936, 775, 919, 158}

    Returns: 2934

  29. {658, 34, 852, 739, 647, 512, 73, 231, 230, 838, 304, 596, 99, 929, 927, 528, 583, 352, 254, 233, 870, 236, 578, 666, 598, 309}

    Returns: 2726

  30. {922, 39, 855, 371, 806, 953, 606, 38, 7, 814, 675, 938, 481, 224, 227, 914, 13, 912, 536, 799, 676, 159, 851, 718, 406, 625, 92}

    Returns: 2813

  31. {148, 376, 990, 568, 366, 732, 22, 858, 553, 515, 217, 532, 778, 285, 944, 260, 188, 856, 371, 356, 84, 631, 400, 585, 610, 962, 797, 973}

    Returns: 2925

  32. {30, 595, 706, 104, 61, 217, 742, 961, 503, 101, 860, 19, 117, 202, 177, 27, 404, 233, 341, 589, 177, 626, 812, 926, 800, 840, 200, 556, 573}

    Returns: 2747

  33. {955, 229, 993, 6, 353, 88, 223, 75, 974, 981, 645, 539, 927, 995, 975, 636, 455, 678, 957, 639, 153, 842, 610, 805, 4, 550, 572, 50, 452, 452}

    Returns: 2969

  34. {731, 621, 677, 52, 106, 937, 875, 104, 907, 435, 133, 487, 23, 263, 671, 993, 163, 138, 287, 780, 142, 102, 343, 521, 919, 982, 953, 782, 83, 38, 865}

    Returns: 2928

  35. {201, 923, 85, 980, 685, 685, 642, 846, 268, 273, 600, 121, 674, 340, 568, 833, 753, 489, 305, 621, 694, 723, 359, 32, 416, 127, 317, 221, 208, 470, 352, 537}

    Returns: 2749

  36. {961, 369, 625, 458, 750, 205, 134, 222, 242, 478, 551, 606, 40, 991, 688, 185, 191, 207, 119, 29, 770, 271, 292, 104, 930, 592, 784, 724, 488, 906, 499, 969, 498}

    Returns: 2921

  37. {144, 102, 469, 697, 943, 282, 487, 725, 356, 19, 73, 502, 173, 20, 355, 152, 271, 832, 891, 641, 823, 394, 579, 867, 845, 394, 403, 793, 851, 397, 109, 95, 275, 343}

    Returns: 2701

  38. {424, 762, 390, 816, 388, 201, 585, 8, 300, 615, 777, 856, 754, 78, 719, 735, 580, 250, 79, 901, 244, 503, 922, 488, 669, 503, 860, 464, 201, 908, 376, 321, 840, 510, 863}

    Returns: 2731

  39. {821, 922, 154, 151, 427, 406, 448, 808, 584, 619, 567, 418, 448, 475, 151, 578, 433, 320, 410, 99, 397, 678, 296, 953, 786, 472, 757, 321, 167, 959, 233, 237, 861, 205, 357, 996}

    Returns: 2908

  40. {63, 744, 389, 437, 216, 578, 382, 315, 352, 413, 916, 748, 482, 291, 432, 228, 69, 955, 262, 647, 117, 504, 295, 44, 133, 891, 887, 229, 996, 409, 404, 554, 785, 8, 561, 245, 28}

    Returns: 2867

  41. {202, 55, 400, 466, 796, 127, 338, 756, 177, 878, 961, 365, 431, 53, 434, 606, 843, 260, 836, 560, 208, 699, 858, 845, 602, 437, 935, 268, 721, 345, 803, 527, 977, 486, 636, 82, 14, 226}

    Returns: 2873

  42. {904, 259, 493, 991, 262, 552, 838, 75, 461, 473, 654, 466, 652, 787, 464, 498, 753, 22, 931, 811, 533, 4, 575, 969, 908, 183, 137, 887, 554, 125, 646, 602, 89, 394, 724, 399, 768, 755, 516}

    Returns: 2891

  43. {514, 125, 530, 148, 980, 282, 611, 481, 823, 877, 722, 713, 786, 394, 838, 278, 572, 748, 126, 799, 430, 48, 207, 497, 10, 610, 103, 298, 546, 305, 25, 926, 182, 621, 645, 218, 166, 217, 91, 542}

    Returns: 2783

  44. {1000, 211, 148, 232, 390, 249, 486, 427, 623, 70, 434, 903, 480, 889, 595, 602, 983, 382, 556, 131, 284, 318, 662, 575, 565, 186, 62, 741, 388, 389, 904, 820, 46, 503, 114, 132, 131, 357, 230, 1, 934}

    Returns: 2917

  45. {878, 101, 332, 288, 321, 157, 469, 821, 114, 703, 747, 970, 819, 87, 947, 8, 759, 185, 727, 330, 258, 396, 85, 552, 620, 694, 352, 590, 84, 788, 181, 492, 945, 876, 260, 458, 564, 881, 998, 975, 409, 314}

    Returns: 2943

  46. {653, 14, 988, 736, 607, 310, 689, 513, 612, 701, 708, 542, 927, 88, 918, 413, 602, 673, 401, 276, 137, 894, 387, 971, 777, 394, 150, 708, 465, 722, 24, 530, 366, 422, 318, 859, 837, 33, 395, 988, 338, 127, 759}

    Returns: 2947

  47. {775, 901, 419, 322, 19, 540, 770, 648, 233, 739, 775, 111, 982, 528, 756, 467, 362, 115, 762, 114, 555, 746, 709, 811, 814, 868, 334, 594, 188, 43, 678, 974, 549, 964, 124, 124, 548, 683, 844, 276, 287, 695, 365, 273}

    Returns: 2920

  48. {41, 740, 844, 191, 197, 296, 162, 284, 313, 741, 639, 488, 437, 685, 873, 721, 351, 540, 925, 687, 476, 63, 608, 863, 276, 370, 371, 275, 43, 143, 273, 366, 176, 75, 455, 166, 572, 794, 343, 386, 792, 683, 344, 946, 723}

    Returns: 2744

  49. {622, 413, 509, 775, 585, 688, 29, 719, 250, 819, 912, 959, 919, 811, 96, 312, 97, 706, 610, 606, 887, 199, 524, 888, 999, 940, 711, 292, 991, 780, 995, 780, 993, 975, 522, 105, 109, 803, 20, 330, 305, 1, 138, 369, 372, 921}

    Returns: 2987

  50. {503, 994, 680, 370, 272, 433, 533, 114, 365, 503, 386, 951, 47, 585, 838, 288, 641, 789, 805, 730, 547, 705, 534, 147, 113, 538, 881, 269, 938, 246, 86, 7, 388, 822, 456, 342, 293, 132, 145, 211, 509, 197, 423, 794, 255, 162, 812}

    Returns: 2883

  51. {358, 374, 697, 451, 228, 780, 499, 518, 810, 142, 682, 805, 515, 739, 473, 25, 27, 395, 808, 614, 338, 244, 330, 166, 430, 328, 980, 83, 209, 227, 989, 540, 100, 992, 757, 953, 879, 794, 371, 498, 350, 552, 454, 961, 617, 354, 560, 480}

    Returns: 2961

  52. {512, 456, 738, 997, 993, 538, 336, 642, 296, 74, 403, 544, 1, 662, 156, 76, 557, 305, 203, 370, 423, 665, 157, 366, 482, 747, 267, 217, 657, 746, 877, 560, 506, 599, 730, 473, 144, 915, 762, 799, 747, 215, 75, 213, 614, 820, 45, 774, 485}

    Returns: 2905

  53. {559, 778, 98, 601, 108, 364, 581, 738, 587, 741, 746, 768, 168, 429, 341, 165, 964, 588, 558, 466, 345, 437, 738, 141, 747, 346, 627, 92, 202, 866, 399, 872, 92, 388, 574, 801, 720, 134, 77, 386, 364, 374, 927, 913, 135, 268, 491, 718, 91, 163}

    Returns: 2804

  54. {1,2,3}

    Returns: -1

  55. {1,3,2}

    Returns: -1

  56. {2,1,3}

    Returns: -1

  57. {2,3,1}

    Returns: -1

  58. {3,1,2}

    Returns: -1

  59. {3,2,1}

    Returns: -1

  60. {1,2,4}

    Returns: -1

  61. {1,4,2}

    Returns: -1

  62. {2,1,4}

    Returns: -1

  63. {2,4,1}

    Returns: -1

  64. {4,1,2}

    Returns: -1

  65. {4,2,1}

    Returns: -1

  66. {2,3,4}

    Returns: 9

  67. {2,4,3}

    Returns: 9

  68. {3,2,4}

    Returns: 9

  69. {3,4,2}

    Returns: 9

  70. {4,2,3}

    Returns: 9

  71. {4,3,2}

    Returns: 9

  72. {193, 820, 51, 523, 766, 833, 275, 252, 40, 686, 36, 288, 555, 971, 710, 557, 169, 267, 760, 517, 888, 254, 995, 229, 349, 825, 700, 383, 318, 311, 713, 467, 197, 658, 283, 817, 81, 58, 65, 556, 775, 625, 565, 683, 565, 72, 352, 833, 719, 282}

    Returns: 2854

  73. {968, 999, 395, 115, 82, 787, 502, 828, 395, 400, 177, 646, 760, 953, 695, 560, 37, 898, 965, 919, 410, 422, 420, 512, 682, 991, 163, 741, 413, 461, 652, 26, 646, 206, 825, 732, 566, 238, 352, 685, 415, 539, 10, 142, 453, 320, 809, 521, 70, 388}

    Returns: 2958

  74. {463, 953, 835, 526, 395, 664, 710, 320, 975, 605, 723, 421, 765, 481, 987, 823, 312, 652, 300, 233, 822, 169, 404, 606, 531, 114, 28, 957, 441, 849, 82, 370, 331, 5, 142, 154, 593, 429, 238, 978, 286, 84, 757, 843, 581, 873, 518, 30, 82, 129}

    Returns: 2940

  75. {966, 657, 693, 652, 551, 116, 664, 321, 841, 315, 554, 998, 132, 439, 757, 256, 312, 619, 801, 795, 637, 664, 835, 382, 679, 574, 600, 527, 184, 679, 388, 487, 873, 393, 768, 177, 692, 649, 167, 508, 801, 750, 489, 690, 56, 329, 768, 372, 998, 199}

    Returns: 2962

  76. {960, 741, 264, 744, 836, 344, 860, 327, 667, 30, 960, 942, 514, 96, 90, 582, 507, 853, 134, 432, 842, 744, 430, 59, 8, 706, 763, 578, 297, 127, 402, 217, 736, 120, 10, 660, 139, 772, 762, 828, 97, 139, 288, 455, 743, 561, 395, 931, 466, 964}

    Returns: 2884

  77. {730, 999, 118, 698, 429, 421, 37, 17, 937, 360, 340, 356, 466, 694, 639, 223, 1000, 154, 565, 304, 220, 305, 110, 370, 148, 934, 888, 975, 42, 572, 425, 921, 75, 352, 991, 45, 683, 153, 468, 44, 213, 589, 181, 455, 896, 801, 449, 343, 102, 916}

    Returns: 2990

  78. {382, 743, 574, 609, 374, 734, 209, 583, 722, 213, 217, 270, 101, 473, 606, 504, 681, 885, 426, 106, 135, 391, 524, 782, 135, 389, 338, 342, 832, 668, 655, 623, 649, 21, 204, 344, 910, 332, 355, 509, 246, 950, 22, 820, 305, 47, 62, 115, 879, 174}

    Returns: 2745

  79. {552, 172, 516, 165, 561, 663, 936, 528, 498, 874, 98, 705, 295, 943, 660, 142, 426, 322, 809, 568, 301, 622, 947, 537, 852, 803, 42, 817, 960, 261, 839, 516, 847, 548, 110, 131, 945, 404, 930, 302, 950, 849, 850, 859, 67, 808, 889, 806, 516, 916}

    Returns: 2857

  80. {499, 925, 475, 492, 932, 471, 830, 230, 347, 136, 783, 842, 403, 83, 373, 397, 562, 93, 31, 729, 49, 674, 1, 917, 652, 830, 503, 534, 213, 610, 614, 610, 233, 72, 98, 220, 460, 205, 818, 545, 120, 411, 424, 694, 584, 488, 588, 868, 154, 646}

    Returns: 2774

  81. {312, 537, 523, 488, 998, 36, 949, 405, 582, 797, 764, 108, 812, 279, 878, 469, 118, 915, 664, 624, 467, 113, 293, 628, 342, 5, 785, 430, 506, 972, 172, 275, 456, 802, 595, 996, 427, 842, 176, 542, 549, 697, 753, 386, 546, 319, 470, 767, 754, 819}

    Returns: 2966

  82. {4, 714, 924, 465, 342, 728, 734, 11, 572, 296, 593, 650, 931, 336, 641, 983, 932, 82, 603, 882, 241, 426, 831, 733, 105, 319, 44, 319, 125, 603, 195, 761, 99, 33, 219, 390, 488, 531, 11, 643, 619, 188, 759, 865, 492, 584, 242, 251, 99, 542}

    Returns: 2846

  83. {978, 712, 141, 832, 1000, 335, 832, 399, 78, 522, 656, 477, 548, 137, 931, 24, 235, 19, 590, 960, 642, 51, 971, 62, 679, 477, 282, 392, 37, 459, 603, 597, 707, 385, 646, 858, 486, 129, 34, 310, 605, 20, 658, 728, 946, 326, 134, 707, 848, 461}

    Returns: 2949

  84. {733, 68, 359, 717, 535, 72, 260, 738, 401, 580, 478, 508, 938, 866, 756, 728, 538, 204, 730, 769, 587, 193, 227, 314, 599, 417, 904, 998, 73, 871, 526, 542, 447, 650, 557, 215, 533, 799, 156, 142, 597, 639, 490, 880, 970, 225, 152, 610, 333, 780}

    Returns: 2906

  85. {459, 961, 102, 586, 437, 79, 916, 780, 299, 84, 175, 518, 329, 933, 626, 535, 640, 203, 719, 376, 298, 850, 755, 742, 21, 268, 680, 366, 187, 826, 129, 116, 979, 294, 984, 599, 31, 416, 275, 236, 22, 995, 118, 990, 132, 75, 538, 183, 334, 598}

    Returns: 2969

  86. {322, 734, 890, 820, 870, 453, 834, 548, 304, 701, 361, 84, 548, 488, 590, 268, 701, 643, 62, 248, 147, 438, 422, 921, 736, 818, 677, 966, 9, 829, 48, 860, 810, 925, 720, 39, 778, 263, 126, 732, 118, 322, 566, 77, 377, 901, 737, 119, 801, 26}

    Returns: 2812

  87. {92, 444, 773, 222, 718, 248, 898, 309, 823, 226, 125, 535, 628, 985, 963, 281, 744, 48, 780, 17, 716, 496, 389, 786, 886, 424, 773, 591, 319, 259, 143, 184, 510, 719, 215, 487, 907, 181, 528, 390, 814, 178, 905, 422, 926, 913, 480, 982, 653, 746}

    Returns: 2930

  88. {662, 398, 304, 163, 563, 119, 357, 818, 706, 634, 285, 452, 637, 121, 497, 629, 795, 574, 881, 428, 54, 590, 934, 762, 569, 233, 977, 456, 838, 888, 109, 18, 214, 124, 784, 379, 850, 951, 919, 94, 782, 665, 143, 198, 133, 10, 175, 699, 560, 142}

    Returns: 2862

  89. {442, 377, 767, 650, 156, 159, 954, 10, 842, 233, 977, 132, 27, 995, 248, 788, 485, 122, 870, 453, 160, 632, 781, 169, 696, 612, 716, 478, 942, 564, 543, 85, 541, 752, 88, 439, 602, 356, 807, 398, 564, 666, 517, 197, 235, 137, 646, 69, 430, 526}

    Returns: 2926

  90. {701, 925, 660, 965, 33, 822, 164, 276, 317, 464, 920, 324, 238, 588, 636, 405, 853, 720, 413, 557, 532, 480, 980, 549, 765, 367, 57, 65, 94, 633, 453, 385, 857, 972, 183, 840, 880, 995, 304, 1000, 78, 766, 539, 912, 744, 882, 100, 532, 506, 184}

    Returns: 2975

  91. {777, 999, 630, 821, 533, 224, 775, 406, 225, 742, 363, 405, 446, 8, 95, 724, 6, 198, 493, 837, 376, 382, 753, 795, 49, 596, 649, 833, 344, 729, 906, 741, 658, 366, 303, 217, 684, 917, 893, 678, 407, 356, 282, 485, 14, 112, 147, 67, 147, 714}

    Returns: 2822

  92. {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987}

    Returns: -1

  93. {1,2,4,8,16,32,64,128,256,512}

    Returns: -1

  94. {1,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987}

    Returns: 3

  95. {999, 1, 1 }

    Returns: -1

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: