onenoughtone

Code Implementation

Profitable Schemes Implementation

Below is the implementation of the profitable schemes:

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * Find the number of profitable schemes.
 * 3D Dynamic Programming approach.
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemes(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 3D DP array
  const dp = Array(m + 1).fill().map(() =>
    Array(n + 1).fill().map(() =>
      Array(minProfit + 1).fill(0)
    )
  );
 
  dp[0][0][0] = 1;  // Base case
 
  for (let i = 1; i <= m; i++) {
    const g = group[i - 1];  // Members required for the current crime
    const p = profit[i - 1];  // Profit generated by the current crime
 
    for (let j = 0; j <= n; j++) {
      for (let k = 0; k <= minProfit; k++) {
        // Exclude the crime
        dp[i][j][k] = dp[i - 1][j][k];
 
        // Include the crime if we have enough members
        if (j >= g) {
          dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
        }
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[m][j][minProfit]) % MOD;
  }
 
  return result;
}
 
/**
 * Find the number of profitable schemes.
 * 2D Dynamic Programming approach (Space Optimization).
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemesOptimized(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 2D DP array
  const dp = Array(n + 1).fill().map(() => Array(minProfit + 1).fill(0));
  dp[0][0] = 1;  // Base case
 
  for (let i = 0; i < m; i++) {
    const g = group[i];  // Members required for the current crime
    const p = profit[i];  // Profit generated by the current crime
 
    for (let j = n; j >= g; j--) {
      for (let k = minProfit; k >= 0; k--) {
        dp[j][k] = (dp[j][k] + dp[j - g][Math.max(0, k - p)]) % MOD;
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[j][minProfit]) % MOD;
  }
 
  return result;
}
 
// Test cases
console.log(profitableSchemes(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemes(10, 5, [2, 3, 5], [6, 7, 8]));  // 7
 
console.log(profitableSchemesOptimized(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemesOptimized(10, 5, [2, 3, 5], [6, 7, 8]));  // 7

Step-by-Step Explanation

Let's break down the implementation:

Understand the Problem: First, understand that we need to find the number of subsets of crimes that generate at least minProfit profit and require at most n members.
Define the State: Define the state dp[i][j][k] as the number of schemes when considering the first i crimes, using exactly j members, and generating at least k profit.
Define the Recurrence Relation: For each crime, we have two options: include it or exclude it. The recurrence relation is dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])] if j >= group[i-1].
Handle Base Cases: Set dp[0][0][0] = 1 as the base case, which means there is one way to achieve 0 profit with 0 members when considering 0 crimes (by doing nothing).
Calculate the Final Answer: Calculate the final answer as the sum of dp[m][j][minProfit] for all j from 0 to n, modulo 10^9 + 7.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the profitable schemes solution in different programming languages.

Profitable Schemes Implementation

Below is the implementation of the profitable schemes in different programming languages. Select a language tab to view the corresponding code.

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * Find the number of profitable schemes.
 * 3D Dynamic Programming approach.
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemes(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 3D DP array
  const dp = Array(m + 1).fill().map(() =>
    Array(n + 1).fill().map(() =>
      Array(minProfit + 1).fill(0)
    )
  );
 
  dp[0][0][0] = 1;  // Base case
 
  for (let i = 1; i <= m; i++) {
    const g = group[i - 1];  // Members required for the current crime
    const p = profit[i - 1];  // Profit generated by the current crime
 
    for (let j = 0; j <= n; j++) {
      for (let k = 0; k <= minProfit; k++) {
        // Exclude the crime
        dp[i][j][k] = dp[i - 1][j][k];
 
        // Include the crime if we have enough members
        if (j >= g) {
          dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
        }
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[m][j][minProfit]) % MOD;
  }
 
  return result;
}
 
/**
 * Find the number of profitable schemes.
 * 2D Dynamic Programming approach (Space Optimization).
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemesOptimized(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 2D DP array
  const dp = Array(n + 1).fill().map(() => Array(minProfit + 1).fill(0));
  dp[0][0] = 1;  // Base case
 
  for (let i = 0; i < m; i++) {
    const g = group[i];  // Members required for the current crime
    const p = profit[i];  // Profit generated by the current crime
 
    for (let j = n; j >= g; j--) {
      for (let k = minProfit; k >= 0; k--) {
        dp[j][k] = (dp[j][k] + dp[j - g][Math.max(0, k - p)]) % MOD;
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[j][minProfit]) % MOD;
  }
 
  return result;
}
 
// Test cases
console.log(profitableSchemes(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemes(10, 5, [2, 3, 5], [6, 7, 8]));  // 7
 
console.log(profitableSchemesOptimized(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemesOptimized(10, 5, [2, 3, 5], [6, 7, 8]));  // 7

Step-by-Step Explanation

1Understand the Problem

First, understand that we need to find the number of subsets of crimes that generate at least minProfit profit and require at most n members.

2Define the State

Define the state dp[i][j][k] as the number of schemes when considering the first i crimes, using exactly j members, and generating at least k profit.

3Define the Recurrence Relation

For each crime, we have two options: include it or exclude it. The recurrence relation is dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])] if j >= group[i-1].

4Handle Base Cases

Set dp[0][0][0] = 1 as the base case, which means there is one way to achieve 0 profit with 0 members when considering 0 crimes (by doing nothing).

5Calculate the Final Answer

Calculate the final answer as the sum of dp[m][j][minProfit] for all j from 0 to n, modulo 10^9 + 7.

Language-Specific Notes

javascript

JavaScript's Array.fill().map() is used to create multi-dimensional arrays.
Math.max() is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The scientific notation 1e9 is used to represent 10^9.
The for loop is used to iterate through the crimes, members, and profits.

python

Python's list comprehension [[[0 for _ in range(min_profit + 1)] for _ in range(n + 1)] for _ in range(m + 1)] is used to create 3D arrays.
The max() function is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The ** operator is used to represent exponentiation (10**9 = 10^9).
Python's range() function is used to generate sequences for iteration.

java

Java's multi-dimensional arrays are created using the new keyword.
Math.max() is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The underscore in 1_000_000_007 is used for better readability of large numbers.
Java requires explicit initialization of arrays, which we do with nested for loops.

cpp

C++'s std::vector is used to create multi-dimensional arrays.
std::max() is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The scientific notation 1e9 is used to represent 10^9.
C++ allows initializing vectors with initializer lists, as in {2, 2} and {2, 3}.

Key Takeaways

The problem can be solved using dynamic programming with three dimensions: crimes, members, and profit.
For each crime, we have two options: include it or exclude it, and we need to consider both options.
We need to ensure that we have enough members to commit a crime before including it in our scheme.
The space complexity can be optimized from O(m * n * minProfit) to O(n * minProfit) by using a 2D DP array and updating it in reverse order.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the profitable schemes problem using a different approach than shown above.

Common Edge Cases

No Crimes

Handle the case where there are no crimes (return 1 if minProfit is 0, otherwise return 0).

n = 5, minProfit = 0, group = [], profit = []

Insufficient Members

Handle the case where there are not enough members to commit any crime (return 1 if minProfit is 0, otherwise return 0).

n = 1, minProfit = 1, group = [2, 3], profit = [2, 3]

Zero Profit Required

Handle the case where the minimum profit required is 0 (return 2^m, where m is the number of crimes, if there are enough members).

n = 10, minProfit = 0, group = [1, 2, 3], profit = [1, 2, 3]

Solution Approach All Problems

Problem Solution Code

onenoughtone

Back to Home

onenoughtone

Back to Home

Profitable Schemes - Implementation

Code Implementation

Profitable Schemes Implementation

Below is the implementation of the profitable schemes:

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * Find the number of profitable schemes.
 * 3D Dynamic Programming approach.
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemes(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 3D DP array
  const dp = Array(m + 1).fill().map(() =>
    Array(n + 1).fill().map(() =>
      Array(minProfit + 1).fill(0)
    )
  );
 
  dp[0][0][0] = 1;  // Base case
 
  for (let i = 1; i <= m; i++) {
    const g = group[i - 1];  // Members required for the current crime
    const p = profit[i - 1];  // Profit generated by the current crime
 
    for (let j = 0; j <= n; j++) {
      for (let k = 0; k <= minProfit; k++) {
        // Exclude the crime
        dp[i][j][k] = dp[i - 1][j][k];
 
        // Include the crime if we have enough members
        if (j >= g) {
          dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
        }
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[m][j][minProfit]) % MOD;
  }
 
  return result;
}
 
/**
 * Find the number of profitable schemes.
 * 2D Dynamic Programming approach (Space Optimization).
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemesOptimized(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 2D DP array
  const dp = Array(n + 1).fill().map(() => Array(minProfit + 1).fill(0));
  dp[0][0] = 1;  // Base case
 
  for (let i = 0; i < m; i++) {
    const g = group[i];  // Members required for the current crime
    const p = profit[i];  // Profit generated by the current crime
 
    for (let j = n; j >= g; j--) {
      for (let k = minProfit; k >= 0; k--) {
        dp[j][k] = (dp[j][k] + dp[j - g][Math.max(0, k - p)]) % MOD;
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[j][minProfit]) % MOD;
  }
 
  return result;
}
 
// Test cases
console.log(profitableSchemes(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemes(10, 5, [2, 3, 5], [6, 7, 8]));  // 7
 
console.log(profitableSchemesOptimized(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemesOptimized(10, 5, [2, 3, 5], [6, 7, 8]));  // 7

Step-by-Step Explanation

Let's break down the implementation:

Understand the Problem: First, understand that we need to find the number of subsets of crimes that generate at least minProfit profit and require at most n members.
Define the State: Define the state dp[i][j][k] as the number of schemes when considering the first i crimes, using exactly j members, and generating at least k profit.
Define the Recurrence Relation: For each crime, we have two options: include it or exclude it. The recurrence relation is dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])] if j >= group[i-1].
Handle Base Cases: Set dp[0][0][0] = 1 as the base case, which means there is one way to achieve 0 profit with 0 members when considering 0 crimes (by doing nothing).
Calculate the Final Answer: Calculate the final answer as the sum of dp[m][j][minProfit] for all j from 0 to n, modulo 10^9 + 7.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the profitable schemes solution in different programming languages.

Profitable Schemes Implementation

Below is the implementation of the profitable schemes in different programming languages. Select a language tab to view the corresponding code.

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * Find the number of profitable schemes.
 * 3D Dynamic Programming approach.
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemes(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 3D DP array
  const dp = Array(m + 1).fill().map(() =>
    Array(n + 1).fill().map(() =>
      Array(minProfit + 1).fill(0)
    )
  );
 
  dp[0][0][0] = 1;  // Base case
 
  for (let i = 1; i <= m; i++) {
    const g = group[i - 1];  // Members required for the current crime
    const p = profit[i - 1];  // Profit generated by the current crime
 
    for (let j = 0; j <= n; j++) {
      for (let k = 0; k <= minProfit; k++) {
        // Exclude the crime
        dp[i][j][k] = dp[i - 1][j][k];
 
        // Include the crime if we have enough members
        if (j >= g) {
          dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
        }
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[m][j][minProfit]) % MOD;
  }
 
  return result;
}
 
/**
 * Find the number of profitable schemes.
 * 2D Dynamic Programming approach (Space Optimization).
 *
 * @param {number} n - Number of members
 * @param {number} minProfit - Minimum profit required
 * @param {number[]} group - Number of members required for each crime
 * @param {number[]} profit - Profit generated by each crime
 * @return {number} - Number of profitable schemes
 */
function profitableSchemesOptimized(n, minProfit, group, profit) {
  const MOD = 1e9 + 7;
  const m = group.length;
 
  // Initialize 2D DP array
  const dp = Array(n + 1).fill().map(() => Array(minProfit + 1).fill(0));
  dp[0][0] = 1;  // Base case
 
  for (let i = 0; i < m; i++) {
    const g = group[i];  // Members required for the current crime
    const p = profit[i];  // Profit generated by the current crime
 
    for (let j = n; j >= g; j--) {
      for (let k = minProfit; k >= 0; k--) {
        dp[j][k] = (dp[j][k] + dp[j - g][Math.max(0, k - p)]) % MOD;
      }
    }
  }
 
  // Calculate the final answer
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = (result + dp[j][minProfit]) % MOD;
  }
 
  return result;
}
 
// Test cases
console.log(profitableSchemes(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemes(10, 5, [2, 3, 5], [6, 7, 8]));  // 7
 
console.log(profitableSchemesOptimized(5, 3, [2, 2], [2, 3]));  // 2
console.log(profitableSchemesOptimized(10, 5, [2, 3, 5], [6, 7, 8]));  // 7

Step-by-Step Explanation

1Understand the Problem

First, understand that we need to find the number of subsets of crimes that generate at least minProfit profit and require at most n members.

2Define the State

Define the state dp[i][j][k] as the number of schemes when considering the first i crimes, using exactly j members, and generating at least k profit.

3Define the Recurrence Relation

For each crime, we have two options: include it or exclude it. The recurrence relation is dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])] if j >= group[i-1].

4Handle Base Cases

Set dp[0][0][0] = 1 as the base case, which means there is one way to achieve 0 profit with 0 members when considering 0 crimes (by doing nothing).

5Calculate the Final Answer

Calculate the final answer as the sum of dp[m][j][minProfit] for all j from 0 to n, modulo 10^9 + 7.

Language-Specific Notes

javascript

JavaScript's Array.fill().map() is used to create multi-dimensional arrays.
Math.max() is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The scientific notation 1e9 is used to represent 10^9.
The for loop is used to iterate through the crimes, members, and profits.

python

Python's list comprehension [[[0 for _ in range(min_profit + 1)] for _ in range(n + 1)] for _ in range(m + 1)] is used to create 3D arrays.
The max() function is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The ** operator is used to represent exponentiation (10**9 = 10^9).
Python's range() function is used to generate sequences for iteration.

java

Java's multi-dimensional arrays are created using the new keyword.
Math.max() is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The underscore in 1_000_000_007 is used for better readability of large numbers.
Java requires explicit initialization of arrays, which we do with nested for loops.

cpp

C++'s std::vector is used to create multi-dimensional arrays.
std::max() is used to ensure that the profit index is non-negative.
The % operator is used to take the modulo of the result.
The scientific notation 1e9 is used to represent 10^9.
C++ allows initializing vectors with initializer lists, as in {2, 2} and {2, 3}.

Key Takeaways

The problem can be solved using dynamic programming with three dimensions: crimes, members, and profit.
For each crime, we have two options: include it or exclude it, and we need to consider both options.
We need to ensure that we have enough members to commit a crime before including it in our scheme.
The space complexity can be optimized from O(m * n * minProfit) to O(n * minProfit) by using a 2D DP array and updating it in reverse order.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the profitable schemes problem using a different approach than shown above.

Common Edge Cases

No Crimes

Handle the case where there are no crimes (return 1 if minProfit is 0, otherwise return 0).

n = 5, minProfit = 0, group = [], profit = []

Insufficient Members

Handle the case where there are not enough members to commit any crime (return 1 if minProfit is 0, otherwise return 0).

n = 1, minProfit = 1, group = [2, 3], profit = [2, 3]

Zero Profit Required

Handle the case where the minimum profit required is 0 (return 2^m, where m is the number of crimes, if there are enough members).

n = 10, minProfit = 0, group = [1, 2, 3], profit = [1, 2, 3]

Solution Approach All Problems

Code Implementation

Profitable Schemes Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

Profitable Schemes Implementation

Step-by-Step Explanation

1Understand the Problem

2Define the State

3Define the Recurrence Relation

4Handle Base Cases

5Calculate the Final Answer

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

No Crimes

Insufficient Members

Zero Profit Required

Profitable Schemes - Implementation

Code Implementation

Profitable Schemes Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

Profitable Schemes Implementation

Step-by-Step Explanation

1Understand the Problem

2Define the State

3Define the Recurrence Relation

4Handle Base Cases

5Calculate the Final Answer

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

No Crimes

Insufficient Members

Zero Profit Required

String Problems

String Problems