Statistics

Problem Statement for "FolderSize"

Problem Statement

When files are stored on disk, typically they are stored in "clusters". Each cluster has a fixed size, and the amount of space consumed by a file is always a multiple of the cluster size. Thus, if the cluster size is 100 bytes, a 165 byte file will actually use 200 bytes of storage, resulting in 35 bytes of wasted space.

We want to determine which areas of our disk storage are wasting the most space. You will be given a String[] files, each element of which contains a folder number followed by a space, followed by a file size. You will also be given an int folderCount indicating the total number of folders on our disk. The folders are numbered 0 through folderCount - 1. Finally, you will be given an int clusterSize, indicating how large each disk cluster is.

You are to return a int[], containing exactly folderCount elements, each element of which is the total amount of wasted space for that folder. Each element of the return value corresponds to the folder with the same index.

Definition

Class:
FolderSize
Method:
calculateWaste
Parameters:
String[], int, int
Returns:
int[]
Method signature:
int[] calculateWaste(String[] files, int folderCount, int clusterSize)
(be sure your method is public)

Notes

  • While many systems use a cluster size that is a power of two, no such restriction exists here.
  • There may be folders that have no files in them. (Wasted space for such a folder is 0.)

Constraints

  • clusterSize will be between 1 and 1000000, inclusive
  • folderCount will be between 1 and 50, inclusive
  • files will contain between 0 and 50 elements, inclusive
  • Each element of files will contain between 3 and 50 characters, inclusive
  • Each element of files will be in the form " " (quotes added for clarity)
  • Each value of will be between 0 and folderCount - 1, inclusive
  • Each value of will be between 0 and 1000000, inclusive
  • and may contain leading zeros

Examples

  1. {"0 55", "0 47", "1 86"}

    3

    50

    Returns: { 48, 14, 0 }

    Here, in folder 0, we have two files. The first requires 2 clusters, and wastes 45 bytes, the second uses 1 cluster and only wastes 3 bytes. The waste for folder 0 is 48 bytes. Folder 1 only has a single file, which wastes 14 bytes. Folder 2 has no files in it, and thus wastes 0 bytes.

  2. {"0 123", "2 456", "4 789", "6 012", "8 345"}

    10

    98

    Returns: { 73, 0, 34, 0, 93, 0, 86, 0, 47, 0 }

    Note here that we can use a leading zero in the file size, and that only every other folder even has a file in it.

  3. {}

    5

    100

    Returns: { 0, 0, 0, 0, 0 }

    The cluster size really doesn't matter since our disk is empty.

  4. {"0 93842", "1 493784", "2 43212", "3 99327", "4 456209", "5 947243", "6 59348", "7 58237", "8 5834", "9 492384", "0 58342", "3 538432", "6 1432", "9 453983", "2 4321", "4 583729", "6 6974", "8 9864", "4 43211", "8 38437"}

    10

    22485

    Returns: { 27696, 886, 19922, 14306, 18616, 19612, 44671, 9218, 35805, 20488 }

  5. {"0 393827", "0 439232", "0 482732", "1 937828", "1 482373", "1 472363"}

    2

    1024

    Returns: { 1073, 1836 }

  6. {"0 94382", "0 834324", "00 0834", "01 48343", "49 534211", "37 54327"}

    50

    7634

    Returns: { 17076, 5095, 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, 6745, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 169 }

  7. {"0 0", "0 0", "0 0", "1 0", "2 0", "3 0"}

    4

    1

    Returns: { 0, 0, 0, 0 }

  8. { "0 50", "0 47", "1 86" }

    3

    50

    Returns: { 3, 14, 0 }

  9. { "09 00", "08 50" }

    10

    50

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  10. { "0 2" }

    1

    2

    Returns: { 0 }

  11. { "0 93842", "1 493784", "2 43212", "3 99327", "4 456209", "5 947243", "6 59348", "7 58237", "8 5834", "9 492384", "0 58342", "3 538432", "6 1432", "9 453983", "2 4321", "4 583729", "6 6974", "8 9864", "4 43211", "8 38437" }

    10

    22485

    Returns: { 27696, 886, 19922, 14306, 18616, 19612, 44671, 9218, 35805, 20488 }

  12. { "0 100" }

    1

    100

    Returns: { 0 }

  13. { "0 50" }

    1

    50

    Returns: { 0 }

  14. { "0 10" }

    1

    10

    Returns: { 0 }

  15. { "0 55", "0 0", "1 86" }

    3

    50

    Returns: { 45, 14, 0 }

  16. { "0 50" }

    2

    50

    Returns: { 0, 0 }

  17. { "0 10" }

    2

    5

    Returns: { 0, 0 }

  18. { "0 1000" }

    1

    100

    Returns: { 0 }

  19. { "0 0", "0 47", "1 86" }

    3

    50

    Returns: { 3, 14, 0 }

  20. { "0 0" }

    1

    5

    Returns: { 0 }

  21. { "0 0" }

    1

    50

    Returns: { 0 }

  22. { "0 0" }

    1

    100

    Returns: { 0 }

  23. { "0 1" }

    1

    1

    Returns: { 0 }

  24. { "0 0" }

    1

    20

    Returns: { 0 }

  25. { "0 100" }

    1

    50

    Returns: { 0 }

  26. { "0 50", "0 50", "1 50" }

    3

    50

    Returns: { 0, 0, 0 }

  27. { "1 50", "2 50" }

    3

    50

    Returns: { 0, 0, 0 }

  28. { "0 20" }

    1

    20

    Returns: { 0 }

  29. { "0 120", "2 90", "4 780", "6 012", "8 345" }

    10

    10

    Returns: { 0, 0, 0, 0, 0, 0, 8, 0, 5, 0 }

  30. { "0 0" }

    1

    2

    Returns: { 0 }

  31. { "0 55", "0 47", "1 50" }

    3

    50

    Returns: { 48, 0, 0 }

  32. { "0 123", "2 456", "4 789", "6 012", "8 345" }

    10

    98

    Returns: { 73, 0, 34, 0, 93, 0, 86, 0, 47, 0 }

  33. { "0 1", "0 1" }

    1

    50

    Returns: { 98 }

  34. { "0 50", "0 50", "0 40" }

    3

    10

    Returns: { 0, 0, 0 }

  35. { "0 3" }

    1

    3

    Returns: { 0 }

  36. { "0 5" }

    1

    5

    Returns: { 0 }

  37. { "0 2" }

    1

    1

    Returns: { 0 }

  38. { "0 0" }

    2

    50

    Returns: { 0, 0 }

  39. { "49 55" }

    50

    50

    Returns: { 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, 45 }

  40. { "0 40" }

    1

    40

    Returns: { 0 }

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: