Statistics

Problem Statement for "TrueSpace"

Problem Statement

In some filesystems, the disk space used by a file is not always equal to the file's size. This is because the disk is divided into clusters of equal size, and each cluster can only be used by a single file. For example, if the cluster size is 512 bytes, and we have a file of size 600 bytes, it would have to be stored in two clusters. Those two clusters cannot be shared with any other files, so the file ends up using 1024 bytes of disk space.

You are given a int[] sizes, where each element is the size of a single file, and an int clusterSize, the cluster size of the filesystem. Return the total disk space used by the given files.

Definition

Class:
TrueSpace
Method:
calculateSpace
Parameters:
int[], int
Returns:
long
Method signature:
long calculateSpace(int[] sizes, int clusterSize)
(be sure your method is public)

Constraints

  • sizes will contain between 1 and 50 elements, inclusive.
  • clusterSize will be between 1 and 1,048,576, inclusive.
  • Each element of sizes will be between 0 and 1,000,000,000, inclusive.

Examples

  1. {600}

    512

    Returns: 1024

    From the problem statement.

  2. {16,32,128,128,0}

    32768

    Returns: 131072

    We waste a lot of space here. (Note that we don't need any clusters for a file of size 0.)

  3. {4096, 33792, 76800}

    1024

    Returns: 114688

    We don't waste any space here.

  4. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}

    1048576

    Returns: 50017075200

  5. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}

    1

    Returns: 50000000000

  6. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    8

    Returns: 0

  7. {260844,617641,205960,567972,592354,499766,435409,567914,683671,95617,898318,942144,236648,713334,930102,308390,733928,807120,487516,531978,827868,932072,733863,438663,483441,921054,297557,794280,845828,776964,404638,196631,40792,391314,992076,702782,507926,588927,380611,606595,743208,141150,808570,807098,555953,77029,434842,321403,322303,483226}

    435409

    Returns: 38751401

    a random test case

  8. {4,0,4,7,0,1,1,6,9,0,1,0,0,0,5,5,3,2,10,6,9,7,1,10,1,9,3,3,6,7,1,0,6,1,1,5,7,1,1,10,1,2,1,0,8}

    1761

    Returns: 65157

  9. {95184,49591,61566,0,1,0,14928,98821,0,74699,81899,67145,1,1,46183,57592,51105,88657,70568,57145}

    989570

    Returns: 16822690

  10. {8264189,1678304,2546123,3143781,8383415,6287561,1047928,3336081,8046976,1681698,9519594,1,4177219,2892781,2095855,7687489,9725745,507116,8192860,2398628,3403116,4775636,9791200,6688061,1767458,2095855,1181096,3406157,2441259,0,5239635,9431342,6287561,1243601,2095853,4590207,3384120,9962136}

    1047927

    Returns: 188626860

  11. {1,1,1,0,1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,0,0,1,1,0,1,1,1,1}

    6071

    Returns: 139633

  12. {0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,0,0,0,1,0,1,1,1,1,1}

    1048564

    Returns: 15728460

  13. {2,1,9,8,0,1,6,5,10,1,0,0,2,5,0,1,10}

    613289

    Returns: 7972757

  14. {2849,2609,7712,6187,9246,292,3933,5490,2279,3134,6839,2279,5310,1031,1813,4274,1426,1194,642,5437,6554,689,7189,8111,9975,111,3136,9404,7065,3934,1873,9264,3421}

    285

    Returns: 149055

  15. {75736,21924,71762,46280,55896,69217,0,1,37861,16468,10252,79853,28422,55364,54294,62161,1,65414,73523,73607,80129,43535,52307,1,86981,36152,0,1,55009,0,95196,64312,93191,32720}

    1038883

    Returns: 32205373

  16. {0,6436,1,3184,0,6019,0,9539,4924,5701,3981,3783,6946,814,7864,7302,322,6863,7704,6231,6219,1,1,2830,808,4412,9277,6209,5447,5111,4893,9041,9772,2664,7422,7295,7161,1065,1,9418,3794,2488,4578,7487}

    1020654

    Returns: 41846814

  17. {41552571,2189023,48750723,89780775,61941246,64305865,18075197,56400150,36580334,90523447,76624677,41796371,54209531,26227734,23177751,40461598,96790937}

    6386

    Returns: 869434742

  18. {170958,641239,725015,125092,311707,795288,702462,721616,368305,268087,649661,249379,77743,964335,448234,163559,60999,67387,608976,183624,483057,160720,798623,69468,223396,532694,709209,823233,644148,120776,107203,207951,387007,245242,868725,335423,881404,385756}

    8

    Returns: 16287808

  19. {91,270,0,891,0,1,597,1,824,367,840,540,131,872,855,346,728,1,46,544,535,848,444,543,0,454,93,677,496,818,1,1,217,925,828,630,280,0,336,104,49}

    2251

    Returns: 83287

  20. {0,1,5,4,0,0,9,0}

    12

    Returns: 48

  21. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    955335

    Returns: 0

  22. {25177490,39391337,1000579,69787472,59500353,46934001,27388514,98574592,15008671,33019075,1708468}

    1000578

    Returns: 424245072

  23. {465734,271894,627194,411695,77094,16979,708089}

    6

    Returns: 2578692

  24. {16154172,26619659,85419088,24775197,98515435,8952758,66597958,20586534,76953024,40496276,77111695,16103793,53334523,96908130,64031168,40147364,67921542,86132223,89520593,83145238}

    1

    Returns: 1139426370

  25. {99,29,35,77,49,2,11,62,92,32,0}

    606460

    Returns: 6064600

  26. {7348968,1837242,9186211,7957914,5511727}

    918621

    Returns: 33988977

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

    13

    Returns: 390

  28. {0,0,0,0}

    1025388

    Returns: 0

  29. {84973,98201,98122,31202,10614,1,8125,28855,40976,0}

    182426

    Returns: 1641834

  30. {402652800,414015805,888854904,159383401,397409926,164016172,772356727,842256045,493570471,52571210,664796550}

    1048575

    Returns: 5257555050

  31. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    46642

    Returns: 0

  32. {372361287,933996130,763061840,851140573,405763439,758605145,617122336,110539089,797820511,405789569,746695239}

    1

    Returns: 6762895158

  33. {282,810,249,642,850,239,610,11,374,676,35,529,10}

    3

    Returns: 5331

  34. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    1048576

    Returns: 0

  35. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    1048451

    Returns: 0

  36. {406,582,757,327,311,556,0,479,783,413,1,533,364,267,693,1,761}

    1048570

    Returns: 16777120

  37. {502003109,436254592,835254527,81348026,203738972,825428224,266279671,982783589,310705417,370969856,403092816,278428800,509728922,761200522,559179899,492913152,607601308,105402853,360189568,185604993,706324039,300614758,89822938,302333959,203798279,67100874,478872723,825584767,440827137,572815488,938943268,874566416,31173095}

    128

    Returns: 14910888320

  38. {64878,93250,70744,31677,37206,48614,17526,27120,5432,86798,40250,1,36866,1,83984,15566,69494,42119,12663,21463,21446,1,59258,91652,0,14864,8708,96523,40359,8493,34297,43825}

    395224

    Returns: 12251944

  39. {144278069,935432526,414484048,831920429,333558805,56277155,817121147,408398446,255743118,315491223,729410903,478769580,385977412,486192481,704803166,155116444,744338920,113854088,441568231,868667645,821945948,676509288,374521969,62177762,674111779,116504215,348243085,429260763,732252990,299334232,878286789,380643425,51139663,469632866,574253160,663621198,409342774,296281610,365142854,439213358,118250533,980730889,317990156,124372816}

    1

    Returns: 20225167958

  40. {0,1,1,0,1,0,0,1,1,0,1,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,1,1,1,0,0,1,1,1,1}

    1041550

    Returns: 22914100

  41. {838,1,997,70,0,630,266,1,0,0,787,871,157,630}

    1048574

    Returns: 11534314

  42. {93640,62236}

    733228

    Returns: 1466456

  43. {35536678,78818074,2919768,82895354,28328186,12939086,6583811,34304477,11011915,67205543,93074925,11815602,17014247,97666316,60413401,80038806,10210529,21477448,42056090,51297056,69985438,69841744}

    29

    Returns: 985434703

  44. {271664256,877801168,60315511,664862549,593296544,458377441,488419545,171608010,555699948,357649042,988684408,263224671,115277026,447814752,205903987,57645857,344347064,812566367,646672407,362267872,683920128,588181307,877433228,787367114,571644700,449960297,9658739,468542048,310334135,374705080,645390528,137428459,985797057}

    32

    Returns: 15634461632

  45. {0,0,0,0,0,0}

    290829

    Returns: 0

  46. {6767,8170,6899,4827,1,9019}

    92651

    Returns: 555906

  47. {6710,118,9480,5236,5441,871,9290,2968,6614,6167,1842,1572,7080,8079}

    2

    Returns: 71472

  48. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 50000000000

  49. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 40000000000

  50. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 5000000000

  51. {1000000000, 1000000000 }

    1

    Returns: 2000000000

  52. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 20000000000

  53. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1048576

    Returns: 50017075200

  54. {100 }

    40

    Returns: 120

  55. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    2

    Returns: 7000000000

  56. {600 }

    512

    Returns: 1024

  57. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 8000000000

  58. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 16000000000

  59. {999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 }

    1

    Returns: 42999999957

  60. {1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 4000000000

  61. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 6000000000

  62. {0, 2 }

    652

    Returns: 652

  63. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 43000000000

  64. {90 }

    15

    Returns: 90

  65. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 33000000000

  66. {0, 128, 128, 32, 16 }

    32768

    Returns: 131072

  67. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 10000000000

  68. {0, 0 }

    6

    Returns: 0

  69. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 11000000000

  70. {600, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 11000000600

  71. {1000000000, 1000000000, 1000000000 }

    1

    Returns: 3000000000

  72. {5, 100000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 7100000005

  73. {10 }

    10

    Returns: 10

  74. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 13000000000

  75. {999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 }

    1

    Returns: 49999999950

  76. {4096, 33792, 76800 }

    1024

    Returns: 114688

  77. {513 }

    512

    Returns: 1024

  78. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 21000000000

  79. {16, 32, 128, 128, 0 }

    32768

    Returns: 131072

  80. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1

    Returns: 27000000000

  81. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1000

    Returns: 5000000000

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: