Profitable Schemes

Hard

Google

2 views

Topics:

Dynamic Programming

There is a group of n members, and a list of various crimes they could commit. The i^th crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

Constraints:

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

Profitable Schemes

Hard

Google

2 views

Topics:

Dynamic Programming

There is a group of n members, and a list of various crimes they could commit. The i^th crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

Constraints:

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for `n`, `minProfit`, and the elements within `group` and `profit`?
Can `group` or `profit` arrays be empty, and if so, what should the return value be?
Can the values in the `profit` array be negative or zero? What does a negative profit mean in the context of the problem?
If multiple combinations of crimes achieve `minProfit`, should I count each distinct combination, or only the number of combinations?
Are the `group` and `profit` arrays guaranteed to have the same length?

Brute Force Solution

Approach

The brute force strategy for finding profitable schemes involves trying every possible combination of criminal activities. We want to count how many combinations are both affordable (don't require more people than we have) and profitable (reach the minimum profit target). We explore all possibilities, keeping track of the ones that satisfy our criteria.

Here's how the algorithm would work step-by-step:

Consider each crime as a choice: either we commit it or we don't.
Start by considering no crimes at all. This is our first possibility.
Now, consider committing only the first crime, and then only the second crime, and so on, until we've tried each crime individually.
Next, consider all possible pairs of crimes: crime 1 and 2, crime 1 and 3, crime 2 and 3, and so on.
Continue this pattern, considering all possible sets of three crimes, then four crimes, and so on, until we consider doing all the crimes.
For each possible combination of crimes, calculate the total number of people required and the total profit earned.
Check if the total number of people required is less than or equal to the number of available people, and check if the total profit earned is greater than or equal to the minimum profit requirement.
If both conditions are met, we have found a valid profitable scheme, so increment our count.
After exploring every single combination of crimes, the final count will represent the total number of possible profitable schemes.

Code Implementation

def profitable_schemes_brute_force(
    number_of_people, minimum_profit, group_sizes, profits
):
    number_of_schemes = 0
    number_of_crimes = len(group_sizes)

    # Iterate through all possible combinations of crimes
    for i in range(1 << number_of_crimes):
        people_required = 0
        profit_earned = 0

        # Calculate total people and profit for the current combination
        for crime_index in range(number_of_crimes):
            # Check if crime is included in current combination
            if (i >> crime_index) & 1:

                people_required += group_sizes[crime_index]
                profit_earned += profits[crime_index]

        # Check if the scheme is feasible and profitable
        if people_required <= number_of_people:

            # Count schemes that meet the minimum profit
            if profit_earned >= minimum_profit:
                number_of_schemes += 1

    return number_of_schemes

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The provided solution explores every possible combination of crimes. Given 'n' crimes, each crime can either be included or excluded in a scheme, leading to 2 possibilities for each crime. Therefore, the total number of combinations to check is 2 multiplied by itself 'n' times, which is 2^n. For each of these 2^n combinations, the solution calculates the required people and profit which takes O(n) time in worst case. Thus the overall time complexity is O(n * 2^n), but since exponential part dominates, it is simplified to O(2^n).

Space Complexity

O(1) – The described brute force strategy does not explicitly mention creation of auxiliary data structures like arrays, lists, or hash maps. It primarily involves considering combinations and counting the number of profitable schemes. The space used for temporary variables to store the total number of people required and the total profit earned for each combination is constant, regardless of the number of crimes. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We want to find the number of ways to plan crimes that meet certain conditions (people required and profit generated). Instead of checking every possible combination of crimes, we use a method that builds up solutions from smaller problems. This approach remembers and reuses the results of these smaller sub-problems to avoid unnecessary recalculations, making it much faster.

Here's how the algorithm would work step-by-step:

Imagine we're building a table to store the number of ways to achieve a certain profit with a certain number of people and a limited set of crimes.
The table's dimensions represent the number of people we can use, the minimum profit we need to make, and the number of crimes we can consider so far.
We start filling the table from the beginning. The first entry represents having no people, no profit, and considering no crimes. There's always one way to achieve this: do nothing!
Now, we move crime by crime, filling each cell in the table. For each crime, we have two choices: either include it in our scheme or don't.
If we *don't* include the crime, the number of ways to reach a certain profit with a certain number of people is the same as it was *before* considering this crime.
If we *do* include the crime, we update the number of ways to reach the target profit and people by adding the ways we could have reached a *smaller* profit and used *fewer* people *before* considering this crime.
We need to be careful! If including a crime requires more people than we have available, or generates more profit than required, we can only use the available resources or the targeted required profit.
We continue this process, crime by crime, row by row, and the table gets filled. Each cell accumulates the number of valid schemes we can make.
Once the entire table is filled, the entry in the last cell represents the total number of valid schemes using all available people and all possible crimes to achieve at least the minimum required profit.
Since the number of schemes can be large, remember to use modulo arithmetic to prevent integer overflow.

Code Implementation

def profitable_schemes(number_of_people, minimum_profit,
                         group_sizes, profits):
    number_of_crimes = len(group_sizes)
    modulo = 10**9 + 7

    # dp[i][j][k] represents the number of schemes using first k crimes,
    # with at most j people and making at least i profit.
    dp = [[[0] * (number_of_crimes + 1)
           for _ in range(number_of_people + 1)]
          for _ in range(minimum_profit + 1)]

    dp[0][0][0] = 1

    for crime_index in range(1, number_of_crimes + 1):
        group_size = group_sizes[crime_index - 1]
        profit = profits[crime_index - 1]

        for current_profit in range(minimum_profit + 1):
            for people_available in range(number_of_people + 1):
                # If we don't commit the crime
                dp[current_profit][people_available][crime_index] =
                    dp[current_profit][people_available][crime_index - 1]

                #If we commit the crime, check if we have enough people
                if people_available >= group_size:

                    new_profit = min(minimum_profit,
                                         current_profit + profit)

                    # Add schemes including this crime to existing schemes
                    dp[new_profit][people_available][crime_index] +=                       dp[current_profit][people_available - group_size][crime_index - 1]

                    dp[new_profit][people_available][crime_index] %= modulo

    total_schemes = 0
    # Sum all schemes that meet the minimum profit requirement
    for people_available in range(number_of_people + 1):
        total_schemes += dp[minimum_profit][people_available][number_of_crimes]
        total_schemes %= modulo

    return total_schemes

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n * m * p) – The algorithm uses dynamic programming with a 3D table. The table dimensions are determined by the number of crimes n, the maximum number of people available m, and the minimum required profit p. The algorithm iterates through each crime (n), and for each crime, it iterates through each possible number of people (m) and each possible profit level (p). Therefore, the time complexity is proportional to the product of these three dimensions, resulting in O(n * m * p).

Space Complexity

O(n * minProfit * groupSize) – The dominant space usage comes from the 3D table used for dynamic programming. The table's dimensions are determined by the number of crimes (n), the minimum profit (minProfit), and the number of people available (groupSize). Therefore, the auxiliary space required is proportional to the product of these three dimensions. This results in a space complexity of O(n * minProfit * groupSize).

Edge Cases

Case	How to Handle
n = 0 (no members available)	Return 1 as no members are needed and any profit will satisfy the minProfit requirement.
minProfit = 0 (no profit needed)	All combinations of members are valid schemes, so calculate the number of combinations possible.
group is empty (no crime)	Return 1 as no members are participating in any crime, satisfying minProfit.
profit is empty (no crimes)	This means all crimes yield no profit, so only consider number of people used.
Large n and minProfit, but small group and profit sizes	The DP table should still be bounded by n and minProfit allowing for efficient calculation.
All profits are 0	The problem reduces to finding the number of subsets of group whose sum is less than or equal to n.
Integer overflow in profit calculation or DP table counts	Take the modulo of the number of ways to reach a particular profit and number of people with 10^9 + 7 as specified in the problem.
minProfit is very large, but individual profits are small.	The DP table size for profit can be optimized by clamping profit values to minProfit to avoid unnecessary calculations.