BitStrings | Topcoder Archive

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", "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.
```
{"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.

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

Returns: 5

{"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010"}

Returns: 20

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.