Profitable Schemes - Practice Coding Problems

Profitable Schemes - Problem

Criminal Organization Planning Challenge

You're managing a criminal organization with n members who need to plan their operations strategically. You have a list of potential crimes, where each crime i:
• Generates profit[i] money
• Requires exactly group[i] members to execute

Important constraint: Each member can only participate in one crime - no member can be involved in multiple operations.

Your goal is to find how many different profitable schemes exist. A profitable scheme is any combination of crimes that:
1. Generates at least minProfit total profit
2. Uses at most n total members

Since the answer can be extremely large, return it modulo 10^9 + 7.

Example: With 3 members, minProfit=2, profits=[2,3,1], groups=[2,1,1]
You could choose crime 0 (profit=2, uses 2 members) OR crimes 1+2 (profit=4, uses 2 members) = 2 schemes

Input & Output

example_1.py — Basic Case

$ Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]

› Output: 2

💡 Note: We can form 2 profitable schemes: choose crime 1 alone (profit=3, members=2) OR choose both crimes (profit=5, members=4). Both satisfy minProfit ≥ 3 and members ≤ 5.

example_2.py — Multiple Options

$ Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]

› Output: 7

💡 Note: Multiple combinations work: {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}. Each achieves profit ≥ 5 with members ≤ 10.

example_3.py — Edge Case

$ Input: n = 1, minProfit = 1, group = [1,1,1], profit = [1,1,1]

› Output: 3

💡 Note: With only 1 member available, we can choose any single crime. Each crime uses exactly 1 member and generates profit 1, meeting our minimum requirement.

Constraints

1 ≤ n ≤ 100
0 ≤ minProfit ≤ 100
1 ≤ group.length ≤ 100
1 ≤ group[i] ≤ 100
0 ≤ profit[i] ≤ 100
Note: Each member can participate in at most one crime

Visualization

Tap to expand

Understanding the Visualization

Setup Crew

You have n members available and need at least minProfit total

Evaluate Heists

Each heist has specific member requirements and profit potential

Dynamic Planning

Use DP to count all valid combinations efficiently

Count Schemes

Sum all ways that meet profit goal with available crew

Key Takeaway

🎯 Key Insight: Use 3D DP to efficiently count all valid combinations by tracking members used and minimum profit achieved, avoiding the exponential complexity of brute force enumeration.

Asked in

G Google 45 a Amazon 38 f Meta 32 ⊞ Microsoft 28

The optimal solution uses 3D Dynamic Programming with states tracking crimes considered, members used, and minimum profit achieved. The key insight is to use dp[j][k] representing the number of ways to use exactly j members and achieve at least k profit. We process crimes one by one and update states based on whether to include each crime or not. Time complexity: O(n × m × minProfit).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Subsets)	O(2^m)	O(1)	Generate all possible subsets of crimes and count valid profitable schemes
3D Dynamic Programming (Optimal)	O(n × m × minProfit)	O(n × minProfit)	Use 3D DP with states: crimes considered, members used, minimum profit achieved

Brute Force (Try All Subsets) — Algorithm Steps

Generate all 2^m possible subsets of crimes (where m is number of crimes)
For each subset, calculate total members needed and total profit
Check if members <= n AND profit >= minProfit
Count valid subsets and return count % (10^9 + 7)

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Use bit masks to generate all 2^m subsets of crimes

Calculate Totals

For each subset, sum up total members and total profit

Validate Constraints

Check if members ≤ n and profit ≥ minProfit

Count Valid Schemes

Increment counter for each valid subset

Code -

solution.c — C

#include <stdio.h>

int profitableSchemes(int n, int minProfit, int* group, int groupSize, int* profit, int profitSize) {
    const int MOD = 1000000007;
    int m = groupSize;
    int count = 0;
    
    // Try all 2^m possible subsets
    for (int mask = 0; mask < (1 << m); mask++) {
        int totalMembers = 0;
        int totalProfit = 0;
        
        // Calculate totals for this subset
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                totalMembers += group[i];
                totalProfit += profit[i];
            }
        }
        
        // Check if this subset forms a valid scheme
        if (totalMembers <= n && totalProfit >= minProfit) {
            count++;
        }
    }
    
    return count % MOD;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^m)

We generate 2^m subsets where m is number of crimes, and for each subset we do O(m) work to calculate totals

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for calculations (not counting recursion stack)

✓ Linear Space

42.3K Views

Medium Frequency

~25 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Try All Subsets) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler