Problem Statement
You have candies of several different types. You are given a
For each non-negative integer i, you have an unlimited supply of boxes with volume 2^i. That is, you have boxes with volume 1, 2, 4, 8, and so on.
You are going to pack the candies into boxes. Each type of candies has to be packed into a single box, and you have to use different boxes for different types of candy. The volume of a box must be greater than or equal to the number of candies it contains.
Once you have each type of candies in a box, you want to pack those boxes into larger boxes, until only one box remains. You can only pack two boxes at a time. That is, you can take any two boxes you currently have, get a new box, and put the two old boxes into the new box. This is possible if and only if the volume of the new box is greater than or equal to the sum of volumes of the two old boxes. You always get to choose which two boxes you want to pack together, and how large the new box should be.
To summarize:
- First, you will pack all the candies into boxes.
- Then, you will pack all those boxes into larger boxes, until you are left with a single box that contains everything.
Compute and return the smallest possible volume of the box obtained at the end of packing.
Definition
- Class:
- BoxesDiv2
- Method:
- findSize
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int findSize(int[] candyCounts)
- (be sure your method is public)
Notes
- You may assume that the return value always fits into a signed 32-bit integer variable.
Constraints
- candyCounts will contain between 1 and 100 elements, inclusive.
- Each element of candyCounts will be between 1 and 1000, inclusive.
Examples
{8,8}
Returns: 16
First, you pack each type of candies into a box with volume 8. Then, you pack the two boxes into a single box with volume 16.
{5,6}
Returns: 16
Even though you have fewer candies than in Example 0, you still have to use boxes with volume 8 (or more) to store them.
{1,7}
Returns: 16
Now you could pack the 1 candy into a smaller box, but it will not help: you still have to use a box with volume 16 to store the two boxes with candies.
{1,1,13,1,1}
Returns: 32
{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}
Returns: 1024
{468,335,501}
Returns: 2048
{725,479,359,963,465,706,146,282,828,962,492}
Returns: 8192
{943,828,437,392,605,903,154,293,383,422,717,719,896,448,727,772,539}
Returns: 16384
{913,668,300,36,895,704,812,323,334,674,665}
Returns: 16384
{712,254,869}
Returns: 4096
{645,663,758,38,860,724,742,530,779}
Returns: 16384
{36,191,843,289,107,41,943,265,649,447,806,891,730,371,351,7,102,394}
Returns: 16384
{630,624,85,955,757,841,967,377,932,309}
Returns: 16384
{440,627,324,538,539,119}
Returns: 8192
{930,542,834,116}
Returns: 4096
{659,705,931,978,307,674,387,22,746,925,73,271,830,778,574,98,513,987,291,162,637}
Returns: 16384
{768,656,575,32,53,351,151,942,725,967,431,108,192,8,338,458,288}
Returns: 16384
{384,946,910,210,759,222,589,423,947,507,31,414,169,901,592}
Returns: 16384
{656,411,360,625}
Returns: 4096
{549,484,596,42,603,351,292,837,375,21,597,22,349,200,669,485,282,735,54}
Returns: 16384
{419,939,901,789,128,468,729,894,649,484,808,422,311,618,814,515,310,617,936,452,601}
Returns: 32768
{520,557,799,304,225,9,845,610,990,703,196}
Returns: 16384
{94,344,524,588,315,504,449}
Returns: 8192
{459,619}
Returns: 2048
{797,799}
Returns: 2048
{590,799,10}
Returns: 4096
{473,623,539,293,39,180,191,658,959,192,816,889,157,512,203,635,273,56,329}
Returns: 16384
{363,887,876,434,870,143,845,417}
Returns: 8192
{999,323,652}
Returns: 4096
{700,558,477}
Returns: 4096
{390,76,713,601,511,4,870,862,689,402,790,256,424,3}
Returns: 16384
{183,286,89,427,618,758,833,933,170,155,722,190,977,330,369,693,426,556,435,550,442,513,146,61,719,754,140,424,280,997,688,530,550,438,867,950,194,196,298,417,287,106,489,283,456,735,115,702,317,672,787,264,314,356,186,54,913,809,833,946,314,757,322,559,647,983,482,145,197,223,130,162,536,451,174,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}
Returns: 65536
{825,335,875,373,160,834,71,488,298,519,178,774,271,764,669,193,986,103,481,214,628,803,100,528,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,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}
Returns: 65536
{424,521,903,963,124,597,738,262,196,526,265,261,203,117,31,327,12,772,412,548,154,521,791,925,189,764,941,852,663,830,901,714,959,579,366,8,478,201,59,440,304,761,358,325,478,109,114,888,802,851,461,429,994,385,406,541,112,705,836,357,73,351,824,486,557,217,627,358,527,358,338,272,870,362,897,23,618,113,718,697,586,42,424,130,230,566,560,933,297,856,54,963,585,735,655,973,458,370,533,964}
Returns: 131072
{484,912,636,68,849,676,939,224,143,755,512,742,176,460,826,222,871,627,935,206,784,851,399,280,702,194,735,638,535,557,994,177,706,963,549,882,301,414,642,856,856,143,463,612,878,425,679,753,444,297,674,41,314,876,73,819,611,18,933,113,696,170,832,41,489,686,91,498,590,991,146,354,315,652,741,45,259,336,760,193,606,265,182,504,830,776,609,293,998,550,557,562,628,468,542,130,241,814,175,602}
Returns: 131072
{1}
Returns: 1
{3}
Returns: 4
{1000}
Returns: 1024
{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,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: 131072
{1, 3, 3 }
Returns: 16
{901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000 }
Returns: 131072
{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, 1000, 1000 }
Returns: 65536
{8, 8 }
Returns: 16
{410, 659, 925, 454, 30, 304, 269, 785, 905, 787, 446, 41, 531, 643, 691, 634, 577, 35, 154, 78, 324, 145, 145, 217, 107, 304, 56, 762, 189, 820, 415, 180, 357, 27, 284, 177, 712, 88, 316, 8, 241, 427, 629, 651, 264, 353, 608, 19, 308, 133, 642, 720, 102, 433, 548, 585, 17, 272, 907, 787, 823, 839, 300, 491, 249, 474, 622, 736, 313, 113, 334, 3, 784, 620, 573, 530, 591, 597, 575, 96, 801, 781, 762, 599, 643, 821, 983, 259, 632, 836, 19, 741, 228, 726, 333, 20, 767, 50, 179, 186 }
Returns: 65536
{1, 1 }
Returns: 2
{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, 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: 131072
{1 }
Returns: 1
{1, 4, 8, 8, 8 }
Returns: 32
{1, 1, 1 }
Returns: 4
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1 }
Returns: 32
{17, 17, 17 }
Returns: 128
{4, 1, 2 }
Returns: 8
{1, 7 }
Returns: 16
{800, 475, 369, 390, 10, 962, 229, 798, 698, 631, 450, 222, 565, 211, 457, 739, 744, 140, 32, 741, 360, 866, 789, 153, 111, 746, 794, 265, 886, 420, 40, 685, 247, 408, 427, 608, 369, 655, 757, 418, 637, 206, 992, 553, 768, 800, 292, 512, 940, 323, 604, 651, 189, 392, 803, 651, 489, 948, 915, 375, 720, 306, 411, 318, 66, 189, 925, 434, 195, 681, 204, 832, 239, 547, 384, 6 }
Returns: 65536
{17 }
Returns: 32
{1, 3, 4 }
Returns: 16
{1, 1, 2 }
Returns: 4
{1, 2, 1 }
Returns: 4
{1, 7, 7, 7 }
Returns: 32
{1, 1, 32, 64 }
Returns: 128
{5, 5, 5 }
Returns: 32
{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, 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: 131072
{8, 16, 32, 64 }
Returns: 128
{502, 349, 177, 219, 492, 2, 190, 61, 200, 56, 485, 476, 858, 731, 243, 777, 660, 246, 676, 891, 67, 354, 389, 956, 224, 394, 289, 19, 598, 93, 719, 451, 441, 247, 669, 933, 248, 858, 993, 447, 266, 829, 274, 123, 559, 868, 252, 571, 114 }
Returns: 32768
{1, 1, 1, 8 }
Returns: 16
{16 }
Returns: 16
{1000, 999, 998 }
Returns: 4096
{1, 1, 13 }
Returns: 32
{1, 1, 3, 7 }
Returns: 16