Number of Ways to Earn Points
HardPrompt
There is a test that has n types of questions. You are given an integer target and a 0-indexed 2D integer array types where types[i] = [counti, marksi] indicates that there are counti questions of the ith type, and each one of them is worth marksi points.
Return the number of ways you can earn exactly target points in the exam. Since the answer may be too large, return it modulo 109 + 7.
Note that questions of the same type are indistinguishable.
- For example, if there are
3questions of the same type, then solving the1stand2ndquestions is the same as solving the1stand3rdquestions, or the2ndand3rdquestions.
Example 1:
Input: target = 6, types = [[6,1],[3,2],[2,3]]
Output: 7
Explanation: You can earn 6 points in one of the seven ways:
- Solve 6 questions of the 0th type: 1 + 1 + 1 + 1 + 1 + 1 = 6
- Solve 4 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 1 + 2 = 6
- Solve 2 questions of the 0th type and 2 questions of the 1st type: 1 + 1 + 2 + 2 = 6
- Solve 3 questions of the 0th type and 1 question of the 2nd type: 1 + 1 + 1 + 3 = 6
- Solve 1 question of the 0th type, 1 question of the 1st type and 1 question of the 2nd type: 1 + 2 + 3 = 6
- Solve 3 questions of the 1st type: 2 + 2 + 2 = 6
- Solve 2 questions of the 2nd type: 3 + 3 = 6Example 2:
Input: target = 5, types = [[50,1],[50,2],[50,5]]
Output: 4
Explanation: You can earn 5 points in one of the four ways:
- Solve 5 questions of the 0th type: 1 + 1 + 1 + 1 + 1 = 5
- Solve 3 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 2 = 5
- Solve 1 questions of the 0th type and 2 questions of the 1st type: 1 + 2 + 2 = 5
- Solve 1 question of the 2nd type: 5Example 3:
Input: target = 18, types = [[6,1],[3,2],[2,3]]
Output: 1
Explanation: You can only earn 18 points by answering all questions.
Constraints:
1 <= target <= 1000n == types.length1 <= n <= 50types[i].length == 21 <= counti, marksi <= 50
Approaches
3 approaches with complexity analysis and trade-offs.
This is a fundamental dynamic programming approach that directly models the problem. We use a 2D array, dp[i][j], to store the number of ways to achieve a score of j using the first i types of questions. The solution iterates through each question type and, for each type, considers all possible numbers of questions to solve (from 0 to count_i), summing up the ways from the previous state.
Algorithm
- Create a 2D DP table
dpof size(n + 1) x (target + 1)and initialize it to 0. - Set
dp[0][0] = 1. - Loop through each question type
ifrom 1 ton. - For each type, get its
countandmarks. - Loop through each possible target score
jfrom 0 totarget. - Loop through the number of questions
kto solve for the current type, from 0 tocount. - If the current score
jis sufficient (j >= k * marks), add the ways from the previous statedp[i-1][j - k * marks]todp[i][j]. - Apply modulo at each addition.
- The result is
dp[n][target].
Walkthrough
We define a DP state dp[i][j] which represents the number of ways to earn exactly j points using the first i types of questions (from index 0 to i-1). The state transition is formulated by considering the i-th question type, which has count = types[i-1][0] questions, each worth marks = types[i-1][1] points. To calculate dp[i][j], we can solve k questions of this type, where 0 <= k <= count. The points earned would be k * marks. The remaining j - k * marks points must be formed using the first i-1 types, for which there are dp[i-1][j - k * marks] ways. The recurrence relation is: dp[i][j] = Σ (from k=0 to count) dp[i-1][j - k * marks]. The base case is dp[0][0] = 1, signifying one way to get a score of 0 with zero question types (by solving none). We build the dp table of size (n+1) x (target+1) bottom-up. The final answer is stored in dp[n][target]. The modulo operation is applied at each addition to prevent overflow.
class Solution { public int waysToReachTarget(int target, int[][] types) { int n = types.length; int MOD = 1_000_000_007; int[][] dp = new int[n + 1][target + 1]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { int count = types[i - 1][0]; int marks = types[i - 1][1]; for (int j = 0; j <= target; j++) { for (int k = 0; k <= count; k++) { if (j >= k * marks) { dp[i][j] = (dp[i][j] + dp[i - 1][j - k * marks]) % MOD; } } } } return dp[n][target]; }}Complexity
Time
O(n * target * max_count), where `n` is the number of types, `target` is the target score, and `max_count` is the maximum count for any question type. This is due to three nested loops.
Space
O(n * target) for the 2D DP table.
Trade-offs
Pros
Intuitive and directly follows the problem's combinatorial nature.
Cons
The time complexity is high due to the third nested loop.
Space complexity can be large for high
nandtarget.
Solutions
Solution
class Solution {public int waysToReachTarget(int target, int[][] types) { int n = types.length; final int mod = (int)1 e9 + 7; int[][] f = new int[n + 1][target + 1]; f[0][0] = 1; for (int i = 1; i <= n; ++i) { int count = types[i - 1][0], marks = types[i - 1][1]; for (int j = 0; j <= target; ++j) { for (int k = 0; k <= count; ++k) { if (j >= k * marks) { f[i][j] = (f[i][j] + f[i - 1][j - k * marks]) % mod; } } } } return f[n][target]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.