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

Profitable Schemes

Number: 911

Difficulty: Hard

Paid? No

Companies: Amazon, Google

Problem Description

Given n members and a list of crimes (each with a required number of members and profit generated), count the number of crime subsets (schemes) such that the total profit is at least minProfit and the total number of members used does not exceed n. Return the answer modulo 10^9+7.

Key Insights

  • Use dynamic programming to model the state as (members used, current profit).
  • Since profit can exceed minProfit, cap the profit dimension at minProfit (any excess is treated as meeting the requirement).
  • Iterate over the list of crimes in a reverse order (to avoid overwriting needed previous values).
  • The DP state update involves including or excluding the current crime from the scheme.
  • The answer is the sum over all states where profit is at least minProfit with any number of members.

Space and Time Complexity

Time Complexity: O(number_of_crimes * n * minProfit)
Space Complexity: O(n * minProfit)

Solution

We use a 2D DP approach where dp[member][profit] represents the number of schemes using exactly 'member' people and achieving exactly 'profit' (capped at minProfit). For each crime with required people and profit, we update the dp table in reverse order with respect to the number of people (to avoid double counting usages within the same iteration). The profit index is updated as: newProfit = min(minProfit, current profit + profit from crime) so that any profit above the threshold is treated the same as exactly minProfit. Finally, summing over dp[i][minProfit] for all valid i (i is range [0, n]) gives the final result.

Code Solutions

# Python solution
MOD = 10**9 + 7

def profitableSchemes(n, minProfit, group, profit):
    crimeCount = len(group)
    # dp[people][p] = number of schemes achieving profit 'p' with used members 'people'
    dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # one way to achieve 0 profit with 0 members
    
    # Process each crime
    for idx in range(crimeCount):
        membersNeeded = group[idx]
        profitEarned = profit[idx]
        # iterate backwards for members to avoid reusing the same crime
        for people in range(n, membersNeeded - 1, -1):
            for p in range(minProfit, -1, -1):
                # New profit, not exceeding minProfit as cap
                newProfit = min(minProfit, p + profitEarned)
                # Update dp: add ways by including this crime
                dp[people][newProfit] = (dp[people][newProfit] + dp[people - membersNeeded][p]) % MOD
    # Sum over all ways where profit achieved is at least minProfit (which is dp[...][minProfit])
    totalSchemes = sum(dp[people][minProfit] for people in range(n + 1)) % MOD
    return totalSchemes

# Example usage:
print(profitableSchemes(5, 3, [2,2], [2,3]))  # Output: 2
← Back to All Questions