We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Strength of a Group

Number: 2754

Difficulty: Medium

Paid? No

Companies: Bloomberg

Problem Description

Given an integer array representing student scores, the goal is to select a non-empty subset of students such that the product of their scores (called the group's strength) is maximized.

Key Insights

  • Since the group can be any non-empty subset, every possible combination of scores must be considered.
  • The array may contain positive numbers, negative numbers, and zeros. The presence of negatives may flip the sign of the product.
  • With at most 13 elements, using brute force (i.e., enumerating all subsets) is computationally feasible.
  • Bit manipulation can be utilized to generate all possible non-empty subsets efficiently.

Space and Time Complexity

Time Complexity: O(2^n * n) where n is the length of the array.
Space Complexity: O(1) (ignoring the input space).

Solution

We can solve the problem by enumerating all non-empty subsets using bitmasks. For each bitmask from 1 to 2^n - 1, we compute the product of numbers corresponding to the set bits. We then update the maximum product encountered. This algorithm leverages bit manipulation for subset generation and is efficient due to the small input size (n <= 13).
Key steps include:

  • Loop through each bitmask to represent a subset.
  • For each subset, multiply the selected scores.
  • Keep track of and return the highest product found.

Code Solutions

# Python solution using bitmask enumeration
def max_strength(nums):
    n = len(nums)
    max_product = float('-inf')
    # Iterate through all possible non-empty subsets using bitmask
    for mask in range(1, 1 << n):
        product = 1
        # For each bit in the mask, multiply if the corresponding index is included
        for i in range(n):
            if mask & (1 << i):
                product *= nums[i]
        # Update maximum product if necessary
        max_product = max(max_product, product)
    return max_product

# Example usage:
nums = [3, -1, -5, 2, 5, -9]
print(max_strength(nums))  # Output: 1350
← Back to All Questions