Statistics

Problem Statement for "BitStrings"

Problem Statement

You are given a list of bitstrings (i.e. strings consisting of only 0's and 1's). You also have a number of 0's and 1's at your disposal. You want to know the maximum number of bitstrings in the list that you can create using those 0's and 1's. Of course, once you use a zero or one, you cannot use it again.

Create a class BitStrings that contains a method maxStrings. maxStrings takes a String[] list, an int numZeroes and an int numOnes as input. The method should return the maximum number of strings from list that can be created using numZeroes zeroes and numOnes ones. Again, reusing zeroes and ones is not allowed.

Definition

Class:
BitStrings
Method:
maxStrings
Parameters:
String[], int, int
Returns:
int
Method signature:
int maxStrings(String[] list, int numZeroes, int numOnes)
(be sure your method is public)

Constraints

  • list will contain between 2 and 20 elements inclusive.
  • Each element of list will have a length between 1 and 50 inclusive.
  • Each element of list will contain only the characters '0' and '1'.
  • numZeroes and numOnes will each be between 0 and 500 inclusive.

Examples

  1. {"1", "00", "100"}

    3

    1

    Returns: 2

    Here, you have three 0's and one 1 at your disposal. The best you can do is create the first two bitstrings. Note that if you create the third bitstring, then you cannot construct any other bitstrings because you won't have a sufficient number of 0's and 1's.

  2. {"00", "110", "101"}

    2

    4

    Returns: 2

    In this case, you have 2 0's and 4 1's. Although you can make the first bitstring "00", you then run out of zeroes and cannot make any more; in this case, you can only construct 1 bitstring. You can do better if you leave the first bitstring and construct the last two, giving a final answer of 2.

  3. {"111", "01", "11", "10", "101"}

    3

    9

    Returns: 5

  4. {"00", "000", "00000"}

    0

    100

    Returns: 0

  5. {"110", "01", "1101", "00"}

    2

    3

    Returns: 2

  6. {"1111", "010101", "1010", "1010010101111111111010101011", "111111111111111111111111111111", "10101010010"}

    253

    131

    Returns: 6

  7. {"1111", "010101", "1010", "1010010101111111111010101011", "111111111111111111111111111111", "10101010010"}

    0

    500

    Returns: 2

  8. {"10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010"}

    500

    500

    Returns: 20

  9. {"00", "0000000000", "0000000000000000", "111111111111111111111111111111110", "1111111111111111111111111111111110", "11111111111111111111111111111111110", "111111111111111111111111111111111110", "1111111111111111111111111111111111110", "11111111111111111111111111111111111110", "11111111111111111111111111111111111110", "111111111111111111111111111111111111110", "1111111111111111111111111111111111111110", "11111111111111111111111111111111111111110", "111111111111111111111111111111111111111110", "1111111111111111111111111111111111111111110", "11111111111111111111111111111111111111111110", "111111111111111111111111111111111111111111110", "1111111111111111111111111111111111111111111110", "11111111111111111111111111111111111111111111110", "111111111111111111111111111111111111111111111110"}

    28

    377

    Returns: 12

  10. {"00", "0000000000", "0000000000000000", "111111111111111111110", "1111111111111111111110", "11111111111111111111110", "111111111111111111111110", "1111111111111111111111110", "11111111111111111111111110", "111111111111111111111111110", "1111111111111111111111111110", "11111111111111111111111111110", "111111111111111111111111111110", "1111111111111111111111111111110", "11111111111111111111111111111110", "111111111111111111111111111111110", "1111111111111111111111111111111110", "11111111111111111111111111111111110", "111111111111111111111111111111111110", "1111111111111111111111111111111111110"}

    500

    500

    Returns: 20

  11. {"1010101011111110000010101010100101010000000011111", "10101000000010101011111111111111111110101010000", "11111111111000000000000010101011111111111", "100000000000000000000000000000000000000000000000", "11111111111111010101010000000000000101011111111111", "1010100100001111101001010001110010100000011101011", "1111111000000000000000010101001011111101001010101", "110100101010010101010101010010101011011111101000", "1111111111111111100000000000000000001010100101011", "110010101010010000000000000000000101010010111", "100000000000111111101010010001111111101010100101", "111101010100000000000000000001010111111110101111", "111111111111110000000010101010000000111101010011", "101010010000000111111111111111111110101001010111", "111111111111111000000000000000000000000101010010", "101000000111111111111111111111010100101010100101", "101010100000000000000000001111111111111111101001", "1111111111111111111111111111110000000000000000000", "0000000000000000000000001111111111111101010100101", "0100111111100000000001010101010000000001111110101"}

    489

    437

    Returns: 19

  12. {"10101000000010101011111111111111111110101010000", "11111111111000000000000010101011111111111", "100000000000000000000000000000000000000000000000", "11111111111111010101010000000000000101011111111111", "1010100100001111101001010001110010100000011101011", "1111111000000000000000010101001011111101001010101", "110100101010010101010101010010101011011111101000", "1111111111111111100000000000000000001010100101011", "110010101010010000000000000000000101010010111", "100000000000111111101010010001111111101010100101", "111101010100000000000000000001010111111110101111", "111111111111110000000010101010000000111101010011", "101010010000000111111111111111111110101001010111", "111111111111111000000000000000000000000101010010", "101000000111111111111111111111010100101010100101", "101010100000000000000000001111111111111111101001", "1111111111111111111111111111110000000000000000000", "0000000000000000000000001111111111111101010100101", "0100111111100000000001010101010000000001111110101", "0000111111111111111111111111000000010101010011111"}

    300

    238

    Returns: 11

  13. {"1010111111", "1010100000", "0000010100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010111111", "0000111111", "1010011111", "0111111100", "0001111111", "1011000011", "1000111111", "1111111000", "1110101010", "1010101111", "1011111111", "0010101110"}

    343

    277

    Returns: 20

  14. {"1010101010", "1110101111", "1111111111", "1010111000", "0000101010", "0001010101", "1001111100", "1110101100", "1000000000", "1010111111", "1010100000", "0000010100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010111111"}

    100

    500

    Returns: 18

  15. {"1110101100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010111111", "0000111111", "1010011111", "0111111100", "0001111111", "1011000011", "1000111111", "1111111000", "1110101111", "1111111111", "1010111000", "1010111111", "0000111111", "1010011111"}

    500

    499

    Returns: 20

  16. {"1010101010", "1110101111", "1111111111", "1010111000", "0000101010", "0001010101", "1001111100", "1110101100", "1000000000", "1010111111", "1010100000", "0000010100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010111111", "0000111111", "1010011111"}

    232

    400

    Returns: 20

  17. {"1010101010", "1110101111", "1111111111", "1010111000", "0000101010", "0001010101", "1001111100", "1110101100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010011111", "1000111111", "1111111000", "1110101111", "1111111111", "1010111000"}

    233

    500

    Returns: 19

  18. {"10101000000010101011111111111111111110101010000", "11111111111000000000000010101011111111111", "100000000000000000000000000000000000000000000000", "11111111111111010101010000000000000101011111111111", "1010100100001111101001010001110010100000011101011", "1111111000000000000000010101001011111101001010101", "110100101010010101010101010010101011011111101000", "1111111111111111100000000000000000001010100101011", "110010101010010000000000000000000101010010111", "100000000000111111101010010001111111101010100101", "111101010100000000000000000001010111111110101111", "111111111111110000000010101010000000111101010011", "101010010000000111111111111111111110101001010111", "111111111111111000000000000000000000000101010010", "101000000111111111111111111111010100101010100101", "101010100000000000000000001111111111111111101001", "1111111111111111111111111111110000000000000000000", "0000000000000000000000001111111111111101010100101", "0100111111100000000001010101010000000001111110101", "0000111111111111111111111111000000010101010011111"}

    123

    411

    Returns: 7

  19. {"10101000000010101011111111111111111110101010000", "11111111111000000000000010101011111111111", "100000000000000000000000000000000000000000000000", "11111111111111010101010000000000000101011111111111", "1010100100001111101001010001110010100000011101011", "1111111000000000000000010101001011111101001010101", "110100101010010101010101010010101011011111101000", "111111111111111101010000000000000001010100101011", "110010101010010000000000000000000101010010111", "100000000000111111101010010001111111101010100101", "111101010100000000011100000001010111111110101111", "111111111111110000000010101010000000111101010011", "101010010000000111111111111111111110101001010111", "111111111111111000000000000000000000000101010010", "101000000111111111111111111111010100101010100101", "101010100000000000000000001111111111111111101001"}

    90

    500

    Returns: 5

  20. {"00", "0000000000", "0000000000000000", "111111111111111111110", "1111111111111111111110", "11111111100111111111110", "111111111111111111111110", "1111111000110111111111110", "11111111111110011111111110", "111111111111111101111111110", "1001111111111111110011111110", "11111001111111111111111111110", "111111110000111111111111111110", "1111111111111000011111111111110", "11111111111111111111111111111110", "111111111111111100000001111111110", "1101010101010101010101010101010010", "11111111111100000001111111110000110", "111111111111011111111111111111111110", "1111111101111111111111111111111111110"}

    500

    194

    Returns: 12

  21. {"1010101010", "1110101111", "1111111111", "1010111000", "0000101010", "0001010101", "1001111100", "1110101100", "1000000000", "1010111111", "1010100000", "0000010100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010111111", "0000111111", "1010011111"}

    443

    0

    Returns: 1

  22. {"1010101010", "1110101111", "1111111111", "1010111000", "0000101010", "0001010101", "1001111100", "1110101100", "1000000000", "1010111111", "1010100000", "0000010100", "1000000011", "0000000000", "1010000000", "1111111111", "1001000000", "1010111111", "0000111111", "1010011111"}

    0

    500

    Returns: 2

  23. {"1000000","110","110"}

    6

    4

    Returns: 2

  24. {"10000000000", "110", "110", "110", "110", "110", "110", "110", "110", "110", "110"}

    10

    9

    Returns: 4

  25. {"11111011111", "001", "001", "001", "001", "001", "001", "001", "001", "001", "001"}

    9

    10

    Returns: 4

  26. {"111111111111111111110", "001", "001", "001", "001", "001", "001", "001", "001", "00111111111"}

    19

    20

    Returns: 9

  27. {"00000000000000000000000000000011", "11100000000000000000000", "11100000000000000000000"}

    40

    6

    Returns: 2

  28. {"11111000001111100000111110000011111", "00000000000000000000000000000000001", "00000", "00000", "00000", "00000", "00000", "00000", "00000", "1111111111111111111111111111111111111111111111110"}

    35

    500

    Returns: 7

  29. {"00111111111111111", "10011111111111111", "11001111111111111", "11100111111111111", "11110011111111111", "11111001111111111", "11111100111111111", "11111110011111111", "11111111001111111", "11111111100111111", "11111111110011111", "11111111111001111", "11111111111100111", "11111111111110011", "11111111111111001", "01111111111111111111111111111111111111111111111111", "01111111111111111111111111111111111111111111111111"}

    30

    275

    Returns: 15

  30. {"00111111111111111", "10011111111111111", "11001111111111111", "11100111111111111", "11110011111111111", "11111001111111111", "11111100111111111", "11111110011111111", "11111111001111111", "11111111100111111", "11111111110011111", "11111111111001111", "11111111111100111", "11111111111110011", "11111111111111001", "01111111111111111111111111111111111111111111111111", "01111111111111111111111111111111111111111111111111"}

    31

    225

    Returns: 15

  31. {"00111111111111111", "10011111111111111", "11001111111111111", "11100111111111111", "11110011111111111", "11111001111111111", "11111100111111111", "11111110011111111", "11111111001111111", "11111111100111111", "11111111110011111", "11111111111001111", "11111111111100111", "11111111111110011", "11111111111111001", "01111111111111111111111111111111111111111111111111", "01111111111111111111111111111111111111111111111111"}

    31

    276

    Returns: 16

  32. {"11000000000000000", "01100000000000000", "00110000000000000", "00011000000000000", "00001100000000000", "00000110000000000", "00000011000000000", "00000001100000000", "00000000110000000", "00000000011000000", "00000000001100000", "00000000000110000", "00000000000011000", "00000000000001100", "00000000000000110", "10000000000000000000000000000000000000000000000000", "10000000000000000000000000000000000000000000000000"}

    300

    31

    Returns: 16

  33. {"11000000000000000", "01100000000000000", "00110000000000000", "00011000000000000", "00001100000000000", "00000110000000000", "00000011000000000", "00000001100000000", "00000000110000000", "00000000011000000", "00000000001100000", "00000000000110000", "00000000000011000", "00000000000001100", "00000000000000110", "10000000000000000000000000000000000000000000000000", "10000000000000000000000000000000000000000000000000"}

    400

    471

    Returns: 17

  34. {"11000000000000000", "01100000000000000", "00110000000000000", "00011000000000000", "00001100000000000", "00000110000000000", "00000011000000000", "00000001100000000", "00000000110000000", "00000000011000000", "00000000001100000", "00000000000110000", "00000000000011000", "00000000000001100", "00000000000000110", "10000000000000000000000000000000000000000000000000", "10000000000000000000000000000000000000000000000000"}

    225

    30

    Returns: 15

  35. {"00011110010111", "0001111", "000011111", "00111011011", "011101", "0111", "0011110", "01", "0001", "0000001", "0001", "111111", "11", "110" }

    10

    15

    Returns: 6

  36. {"100", "0", "0010", "00" }

    5

    2

    Returns: 3

  37. {"10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010", "10101010101010101010101010101010101010101010101010" }

    500

    500

    Returns: 20

  38. {"1", "111", "1000", "10", "1000" }

    3

    7

    Returns: 3

  39. {"100", "0101", "01010", "0101011", "1010101", "1101010", "1111111", "11111111", "1010101010101", "101010101010111", "101010111111111", "111010101", "101001", "11101", "111010101", "1011001001", "110101010", "10101010101", "1010101010", "10101011" }

    500

    500

    Returns: 20

  40. {"1", "1", "1", "0", "10" }

    1

    1

    Returns: 2

  41. {"00000", "11111", "10", "10" }

    2

    2

    Returns: 2

  42. {"00", "110", "101" }

    2

    4

    Returns: 2

  43. {"01111", "001", "0011" }

    4

    4

    Returns: 2

  44. {"01111111111111111", "001", "0011" }

    4

    8

    Returns: 2

  45. {"00000", "11111", "10", "10" }

    0

    0

    Returns: 0

  46. {"111", "01", "111", "01", "111", "01" }

    3

    3

    Returns: 3

  47. {"1111100000", "1111100000", "100", "01", "01", "0110" }

    5

    5

    Returns: 3

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: