Statistics

Problem Statement for "FillBox"

Problem Statement

You have a length x width x height box, and you want to fill it with cubes. The cubes have sides that are powers of 2 (1x1x1, 2x2x2, 4x4x4, 8x8x8, etc.). You are given a int[] cubes, the i-th element of which is the number of 2^i x 2^i x 2^i cubes you have (i is a 0-based index). Return the minimum number of cubes necessary to fill the box, or -1 if it is impossible to do so.

Definition

Class:
FillBox
Method:
minCubes
Parameters:
int, int, int, int[]
Returns:
int
Method signature:
int minCubes(int length, int width, int height, int[] cubes)
(be sure your method is public)

Constraints

  • length, width and height will each be between 1 and 10^6, inclusive.
  • cubes will contain between 1 and 20 elements, inclusive.
  • Each element of cubes will be between 0 and 10^6, inclusive.

Examples

  1. 4

    4

    8

    {10,10,10}

    Returns: 2

    In order to cover the 4x4x8 box we need two 4x4x4 cubes.

  2. 4

    4

    8

    {10,10,1}

    Returns: 9

    Same case as before but we have only one 4x4x4 cube so we will use eight 2x2x2 cubes

  3. 10

    10

    11

    {2000}

    Returns: 1100

    We have only 1x1x1 cubes. We will need 1100 of those cubes to cover the whole box.

  4. 10

    10

    11

    {1099}

    Returns: -1

    We don't have enough 1x1x1 cubes.

  5. 37

    42

    59

    {143821,14382,1438,143,14,1}

    Returns: 5061

  6. 524288

    524288

    524288

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}

    Returns: 1

  7. 1

    1

    1

    {0}

    Returns: -1

  8. 464

    464

    464

    {1000000,1000000,1000000,1000000}

    Returns: 195112

  9. 524288

    524288

    524287

    {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    Returns: -1

  10. 163840

    698368

    179200

    {146071,777733,599818,266038,12509,478351,201640,618984,143988,87783,837107,349651,99683,484992,553337,438088,68198,972282,890781,586124}

    Returns: 152390

  11. 826368

    57344

    352256

    {300483,12903,885770,893074,783710,83450,145620,356667,677191,627276,513995,926532,444279,237315,785832,411595,106453,89134,746365,281031}

    Returns: 31584

  12. 372736

    786432

    245760

    {332834,20121,76680,588957,322200,231687,728795,929130,819202,475810,71693,37304,323102,771307,36319,561510,973081,517179,498001,850892}

    Returns: 15960

  13. 106496

    643072

    759808

    {213209,274503,297801,147439,967620,962303,519679,275682,463091,876840,379622,730730,736467,401244,634502,16937,915244,134688,703446,718121}

    Returns: 33264

  14. 30208

    534016

    139264

    {26896,258866,167125,249270,49081,1735,695066,236752,566678,645580,44228,650999,387151,998523,107388,596931,191246,808950,468673,317313}

    Returns: 593131

  15. 524288

    819200

    851968

    {640188,494640,929124,399776,679394,546986,826758,682435,662649,242966,225652,957443,492133,733054,512856,18927,384267,630293,992229,494846}

    Returns: 523

  16. 475136

    292864

    229376

    {605242,385053,297374,988809,730761,242863,983510,962548,531708,46968,522217,859929,695062,523161,22103,550080,164490,925140,215163,82564}

    Returns: 34888

  17. 327680

    224256

    493568

    {786516,991129,530463,289500,818570,474342,540249,463889,193206,88031,249552,982900,674263,436114,129260,989520,740925,358246,831787,250853}

    Returns: 213203

  18. 524288

    565248

    98304

    {153167,305221,502628,367453,778840,358931,709335,736494,9786,522353,791050,936559,619917,594750,320388,594037,795906,876909,179859,40525}

    Returns: 1136

  19. 581632

    720896

    524288

    {48181,387895,196695,528162,788050,997336,538392,665914,987442,727209,816227,483984,686875,875717,370969,220161,559646,726869,288440,799841}

    Returns: 7473

  20. 442368

    879616

    196608

    {21503,875324,908533,750502,813631,860977,289238,986025,774422,645483,415078,874278,198020,247570,700543,440825,38147,304770,957750,893849}

    Returns: 106188

  21. 688128

    264192

    262144

    {784559,756319,446612,981045,328201,727918,55001,858147,512017,591359,321597,454274,555985,516997,289311,168986,113119,672155,891044,836331}

    Returns: 43078

  22. 524288

    294912

    667648

    {799123,297905,343351,715576,454620,501664,177792,643283,161111,356930,38113,208389,307541,71872,859993,646933,134582,54250,909714,210356}

    Returns: 11852

  23. 548864

    507904

    7168

    {384539,424702,498337,706388,27569,75072,730529,748431,344800,864185,807585,550941,557110,715488,116527,138492,649617,253613,928290,785792}

    Returns: 348936

  24. 131072

    819200

    823296

    {176338,320841,954656,235775,540303,647894,244610,452096,4861,266390,412541,523420,178141,8791,65118,557856,395157,466117,221251,177501}

    Returns: 6632

  25. 325632

    624640

    417792

    {753188,681108,928939,817030,676934,505266,100889,34643,139448,310775,216855,438767,124010,874244,439769,560297,621031,448488,328734,254159}

    Returns: 118712

  26. 632064

    136192

    65536

    {284736,284218,945770,195660,60777,768182,812838,972252,399860,846543,161220,697147,217447,636066,253895,307723,451856,400442,873975,635246}

    Returns: 186746

  27. 524288

    151552

    873472

    {291091,950578,162425,423123,534999,989561,638673,474419,517335,435187,596504,530616,818898,333787,624785,826185,769563,242630,423008,438776}

    Returns: 109640

  28. 253952

    622592

    327680

    {747736,598845,885357,56688,899362,919198,860544,105974,218045,773807,848666,333181,315193,678409,369082,659267,153233,886886,305579,357106}

    Returns: 4129

  29. 923648

    69632

    802816

    {251070,498168,501701,633651,965335,667053,935932,878691,878076,396008,379692,152483,843197,27994,67978,836083,757323,345721,393387,300896}

    Returns: 60956

  30. 337920

    49152

    937984

    {487553,0,0,928191,134501,0,0,0,0,0,977350,408348,0,859030,304427,95783,649599,0,0,0}

    Returns: 21008

  31. 811008

    65536

    761856

    {228805,0,0,472408,0,0,88948,219734,0,667790,0,0,248630,221779,71501,0,0,0,580884,0}

    Returns: 10544

  32. 333824

    135168

    516096

    {283564,77392,590113,435779,601494,754825,507409,0,0,771800,710923,482364,160524,654170,0,129117,333401,268914,0,203642}

    Returns: 32858

  33. 163840

    915456

    540672

    {0,0,0,0,31754,638726,554309,0,0,0,0,654027,755529,611469,672973,0,123101,777856,567866,753281}

    Returns: 32598

  34. 691200

    712704

    450560

    {0,402208,0,976710,0,0,220164,0,0,0,970900,0,215534,414737,165193,0,969752,685995,997302,71936}

    Returns: 940973

  35. 835584

    704512

    231424

    {496077,275518,0,0,0,0,0,0,188251,0,0,820551,0,992569,360599,697803,482345,248250,0,757278}

    Returns: 142599

  36. 571392

    389120

    802816

    {156047,0,608750,0,406647,508608,229921,0,0,616768,0,883177,364431,21665,34122,739397,931614,0,821100,0}

    Returns: 134582

  37. 180224

    475136

    557056

    {449997,0,0,0,0,433913,0,210615,428578,0,678977,727959,295095,0,0,0,0,589704,0,611792}

    Returns: 341771

  38. 212992

    47104

    581632

    {0,363308,690474,377751,0,0,0,186251,733443,521186,0,54664,357648,485057,0,771610,638674,647146,93752,223471}

    Returns: 39724

  39. 792064

    311296

    276480

    {0,0,824419,659680,0,0,0,0,0,802024,25116,643220,499028,0,206632,548249,0,644374,40454,52222}

    Returns: 917651

  40. 573440

    577536

    200704

    {341769,0,0,228353,0,872866,0,0,0,0,0,786700,0,220582,0,0,0,0,981167,973864}

    Returns: 329280

  41. 720896

    102400

    319488

    {0,937731,65746,117569,0,0,589274,0,322464,957378,947460,0,722795,0,453403,0,382145,591325,542518,0}

    Returns: 24420

  42. 776192

    651264

    16384

    {23353,0,0,413860,598816,0,328998,763469,0,0,679083,0,983190,700751,583354,0,815777,0,190939,0}

    Returns: 23761

  43. 405504

    685056

    649216

    {0,0,0,0,708622,0,0,32687,0,303838,509629,891821,0,142139,0,803968,325187,0,0,0}

    Returns: 682389

  44. 851968

    850944

    12288

    {142636,0,0,516257,0,0,224348,413283,313676,644095,0,0,671675,267387,828868,0,0,0,0,0}

    Returns: 293800

  45. 689152

    708608

    69632

    {0,348339,0,540032,378625,0,441844,11096,0,403023,0,355015,0,0,633320,0,576251,357456,0,0}

    Returns: 631388

  46. 564224

    968704

    65536

    {0,845139,633491,0,752538,0,924035,0,0,0,938576,812332,201853,960822,236044,518882,384209,0,123557,0}

    Returns: 88562

  47. 620544

    8192

    538112

    {861692,240743,0,741789,0,483966,0,49882,317529,611945,306550,466649,498392,664820,572349,630894,0,0,487410,899762}

    Returns: 30725

  48. 20480

    339968

    258048

    {626265,0,366069,938305,0,0,0,0,0,659054,51607,638650,0,447664,0,0,0,0,45119,353530}

    Returns: 49014

  49. 854016

    122880

    474112

    {760252,46406,0,0,0,0,53255,876128,0,0,569492,856735,200565,428597,0,0,0,0,0,0}

    Returns: 234060

  50. 786432

    876544

    880640

    {860914,258588,233332,384780,541663,556208,354609,180352,620573,520368,610110,237308,410484,54898,459691,32989,754567,277294,138003,257917}

    Returns: 66896

  51. 200192

    8434

    737280

    {969907,558422,672280,411971,201743,391115,804544,122673,332086,224872,250197,430588,781267,504610,933899,81455,585949,704983,633218,218771}

    Returns: -1

  52. 98048

    672512

    182528

    {315349,636117,574099,68572,615267,669997,834269,897396,460384,243644,43052,636535,903709,962805,668598,478387,126863,446716,508721,350769}

    Returns: -1

  53. 30038

    22016

    903872

    {127755,128603,444890,177794,853230,321799,830214,980440,623200,654791,731231,904515,519985,249318,867632,61875,533932,491876,790875,895677}

    Returns: -1

  54. 34736

    386560

    270592

    {439455,744497,639712,890997,322702,608657,545608,735821,489565,891742,377386,938919,354253,947960,652764,802804,279794,983717,888630,335775}

    Returns: -1

  55. 6528

    93376

    144816

    {701511,716861,680614,515923,442793,147729,428404,413661,75567,334418,473284,277149,998424,106214,417348,952735,439979,440685,103226,6227}

    Returns: -1

  56. 704512

    999424

    428032

    {852715,213550,485911,245556,560025,136426,434027,776333,654175,149430,753906,270703,584079,956061,920656,70841,958911,330368,335344,735905}

    Returns: 171663

  57. 39040

    120832

    88064

    {489198,868915,60528,504410,783751,730361,412219,640522,693899,260578,913066,573247,847649,47391,897481,560039,8948,293304,335505,555744}

    Returns: 717506

  58. 749248

    180224

    453760

    {685799,918865,939325,948946,225160,733753,75092,176140,540137,44406,555864,770332,294901,780664,448040,787021,467071,720938,413042,144685}

    Returns: -1

  59. 835584

    377504

    31897

    {666356,675530,9303,80278,247527,164222,870575,295891,888711,667278,468939,32806,834446,850694,600510,39930,245161,240337,153703,814651}

    Returns: -1

  60. 53

    51

    14

    {5417,4054}

    Returns: 9464

  61. 4

    94

    65

    {2263,2784}

    Returns: 4952

  62. 54

    46

    96

    {820,5014,3087}

    Returns: 8885

  63. 93

    84

    64

    {12529,24759,4522}

    Returns: 41769

  64. 10

    7

    9

    {334,5,16,327}

    Returns: 343

  65. 8

    7

    5

    {132,21}

    Returns: 133

  66. 9

    8

    9

    {528,15}

    Returns: 543

  67. 6

    8

    8

    {15,31,2}

    Returns: 41

  68. 1

    6

    4

    {6,13,0}

    Returns: -1

  69. 2

    3

    3

    {2,28,8,34}

    Returns: -1

  70. 1000000

    1000000

    1000000

    {1000000, 4545, 45643, 3454, 345 }

    Returns: -1

  71. 657

    24366

    1235

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  72. 1000000

    1000000

    1000000

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  73. 1000000

    1

    1

    {1000000 }

    Returns: 1000000

  74. 66560

    526336

    270336

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 140464

  75. 1000000

    123

    2

    {1000000, 1000000, 1000000, 1000000, 1000000, 900017, 1000000, 1000000, 1000000, 1000000, 1000000, 100009, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  76. 524288

    524288

    524288

    {1 }

    Returns: -1

  77. 324793

    322543

    436544

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  78. 1000000

    1000000

    1000000

    {1099 }

    Returns: -1

  79. 2048

    2048

    2048

    {1 }

    Returns: -1

  80. 1000000

    1000000

    1000000

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  81. 64

    64

    524288

    {1000000 }

    Returns: -1

  82. 1000000

    1000000

    1000000

    {1000000, 1000000, 1000000, 1000000, 1000000, 800000, 900000, 280000, 0, 0, 0, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  83. 65536

    65536

    1

    {1000000 }

    Returns: -1

  84. 524287

    524287

    524287

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  85. 1

    1

    1

    {143821, 14382, 1438, 143, 14, 1 }

    Returns: 1

  86. 37

    42

    59

    {143821, 14382, 1438, 143, 14, 1 }

    Returns: 5061

  87. 524289

    524288

    524288

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  88. 1000000

    1000000

    1000000

    {1000000 }

    Returns: -1

  89. 99999

    99999

    99999

    {4554, 4, 4, 5, 5, 4545, 5, 4, 5, 4, 544, 4545, 54, 4, 55, 44, 87, 787, 8888 }

    Returns: -1

  90. 262144

    262144

    262144

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 1

  91. 100000

    100000

    100000

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  92. 524288

    524288

    524288

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  93. 97897

    56734

    32424

    {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    Returns: -1

  94. 823

    45

    567

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 583093

  95. 99999

    99999

    99999

    {45542, 4, 22222, 5, 5, 4545, 5, 4, 5, 4, 544, 4545, 54, 4, 55, 44, 87, 787, 8888 }

    Returns: -1

  96. 1

    100000

    40000

    {100000 }

    Returns: -1

  97. 100000

    100000

    100000

    {1000000 }

    Returns: -1

  98. 5

    5

    5

    {109, 1 }

    Returns: -1

  99. 1000000

    1000000

    1000000

    {1000000, 1000000, 1000000, 10, 10, 10 }

    Returns: -1

  100. 1

    65536

    65536

    {1000000 }

    Returns: -1

  101. 1

    1000000

    1

    {1000000 }

    Returns: 1000000

  102. 688128

    500736

    363520

    {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 500000, 500000, 82000, 5, 4000, 100, 1000, 100, 20, 1, 1 }

    Returns: 1342418

  103. 63

    117

    251

    {99999, 99999, 99999, 2, 0, 12 }

    Returns: 81935

  104. 32768

    32768

    32768

    {10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: -1

  105. 10000

    2000

    1000

    {1000000 }

    Returns: -1

  106. 3

    3

    3

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 20

  107. 1000000

    1

    1

    {1000000, 1000000, 1000000, 1000000 }

    Returns: 1000000

  108. 1000000

    1000000

    1

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: -1

  109. 1000000

    1000000

    1000000

    {1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  110. 65536

    65536

    1

    {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    Returns: -1

  111. 65536

    999999

    65536

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: -1

  112. 1

    1000000

    1000000

    {1000000 }

    Returns: -1

  113. 482928

    554607

    135730

    {466583, 980409, 178559, 43021, 959429, 435920, 408967, 989235, 490736, 773889, 247523, 568911, 69401, 91407, 582871, 119965 }

    Returns: -1

  114. 1000000

    3000

    1

    {0, 0 }

    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: