Solving the Weekly Challenge 302 Task 1: Ones and Zeroes in Python

1. Introduction

The Weekly Challenge, organized by Mohammad S. Anwar, is a friendly competition in which developers compete by solving a pair of tasks. It encourages participation from developers of all languages and levels through learning, sharing, and having fun.

Task 1: Ones and Zeroes from The Weekly Challenge tasks developers to find the largest subset that contains at most x zeroes and y ones.

In this post I discuss, and present my Python language solution to, Task 1: Ones and Zeroes, and wrap with a brief conclusion.

2. Task 1: Ones and Zeroes

You are given an array of binary strings, @str, and two integers, $x and $y.

Write a script to return the size of the largest subset of @str such that there are at most $x 0's and $y 1's in the subset.

A set m is a subset of n if all elements of m are also elements of n.

The Weekly Challenge 302, Task 1: Ones and Zeroes

Examples 1 and 2 present the expected outputs from given inputs.

Example 1

Input: @str = ("10", "0001", "111001", "1", "0")
       $x = 5
       $y = 3
Output: 4

The largest subset with at most five 0's and three 1's: ("10", "0001", "1", "0").

Example 2

Input: @str = ("10", "1", "0")
       $x = 1
       $y = 1
Output: 2

The largest subset with at most one 0's and one 1's: ("1", "0").

3. My solution to Task 1

from itertools import combinations

def return_subset(strs: list[list], x: int, y: int) -> int | None:
    for r in range(len(strs) - 1, 1, -1):
        subsets = combinations(strs, r)
        for subset in subsets:
            total_zeros = 0
            total_ones = 0
            for element in subset:
                total_zeros += element.count('0')
                total_ones += element.count('1')
            if total_zeros <= x and total_ones <= y:
                return len(subset)
    return None

My solution uses itertools.combinations, for loops, and if statements to find the subset that matches the task requirements:

• I use the combinations function to generate all subsets of strs with length r. I start with the maximum subset length, r = len(strs) - 1 and decrement to the smallest subset length, r = 1.
• For each subset of length r
  • I count the total number of zeros (total_zeros) in the subset.
  • I count the total number of ones (total_ones) in the subset.
  • I return the length of subset if it matches the required conditions (total_zeros <= x and total_ones <= y).
• If there are no subsets of strs, then I return None.

4. Conclusion

In this post I discussed Task 1: Ones and Zeroes, and I presented my solution to this task.

Learn more about the latest and past challenges at The Weekly Challenge website:
https://theweeklychallenge.org/

Learn more about competing at The Weekly Challenge FAQ:
https://theweeklychallenge.org/faq/