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.
This approach refines the brute-force DP by reducing its space complexity. Observing that the calculation for the current question type i only depends on the results from the immediately preceding type i-1, we can avoid storing the entire 2D DP table. Instead, we use only two 1D arrays: one for the previous state and one for the current state.
Algorithm
- Initialize a 1D array
dpof sizetarget + 1, withdp[0] = 1. - Loop through each question type
ifrom 0 ton-1. - Create a temporary array
new_dpof sizetarget + 1, initialized to 0. - Get
countandmarksfor typei. - Loop through each score
jfrom 0 totarget. - Loop through
kfrom 0 tocount. - If
j >= k * marks, updatenew_dp[j]by addingdp[j - k * marks]. - After the inner loops, assign
new_dptodp. - The final answer is
dp[target].
Walkthrough
Instead of a (n+1) x (target+1) table, we use two 1D arrays, dp and new_dp, both of size target+1. dp stores the results for the previous type, and new_dp is used to compute the results for the current type. We initialize dp[0] = 1 and all other elements of dp to 0. We iterate through each question type. In each iteration, we calculate new_dp based on the values in dp. The update rule remains the same: new_dp[j] = Σ (from k=0 to count) dp[j - k * marks]. After processing all scores j for the current type, the new_dp array holds the complete results for this stage. We then assign new_dp to dp to prepare for the next question type. This cycle of computing new_dp from dp and then updating dp continues for all question types.
class Solution { public int waysToReachTarget(int target, int[][] types) { int n = types.length; int MOD = 1_000_000_007; int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 0; i < n; i++) { int count = types[i][0]; int marks = types[i][1]; int[] new_dp = new int[target + 1]; for (int j = 0; j <= target; j++) { for (int k = 0; k <= count; k++) { if (j >= k * marks) { new_dp[j] = (new_dp[j] + dp[j - k * marks]) % MOD; } } } dp = new_dp; } return dp[target]; }}Complexity
Time
O(n * target * max_count). The time complexity is not improved, as the three nested loops structure is maintained.
Space
O(target), as we only need two arrays of size `target + 1` to store DP states.
Trade-offs
Pros
Significantly reduces memory usage, making it feasible for problems with larger
nortargetwhere memory might be a constraint.
Cons
The time complexity remains the bottleneck, identical to the non-space-optimized version.
This is the most efficient solution, which improves the time complexity by eliminating the innermost loop of the brute-force DP. The summation Σ dp[j - k * marks] is recognized as a form of sliding window sum, which can be computed in O(1) time for each state by using a clever recurrence relation.
Algorithm
- Initialize a 1D array
dpof sizetarget + 1, withdp[0] = 1. - Loop through each question type
(count, marks). - Create a temporary array
new_dpof sizetarget + 1. - Loop through each score
jfrom 0 totarget. - Calculate
new_dp[j]using the optimized recurrence:ways = dp[j](ways from previous types).- If
j >= marks, addnew_dp[j - marks]toways. - If
j >= (count + 1) * marks, subtractdp[j - (count + 1) * marks]fromways. - Remember to handle modulo and potential negative results.
- Store the result in
new_dp[j].
- After the inner loop, assign
new_dptodp. - The final answer is
dp[target].
Walkthrough
This approach also uses a 1D DP array dp that is updated for each question type. Let dp_prev be the DP array before considering the current type and dp_curr be the array after. The core recurrence dp_curr[j] = Σ (from k=0 to count) dp_prev[j - k * marks] is optimized. We can establish a relationship: dp_curr[j] = dp_prev[j] + dp_curr[j - marks] - dp_prev[j - (count + 1) * marks]. Let's break down this formula:
dp_prev[j]: This is the number of ways to get scorejwithout using the current question type at all (i.e., solving 0 questions of this type).dp_curr[j - marks]: This term represents the number of ways to get scorej-marksusing the types up to the current one. It cleverly accumulates the sums for us. It representsΣ (from k=0 to count) dp_prev[j - marks - k * marks].dp_prev[j - (count + 1) * marks]: Thedp_curr[j - marks]term effectively assumes we can take an unlimited number of questions of the current type. We must subtract the cases where we take more thancountquestions. This term removes the ways corresponding to takingcount + 1or more questions. By iteratingjfrom 0 totarget, we can computedp_currusingdp_prevand previously computed values ofdp_currin O(1) per state.
class Solution { public int waysToReachTarget(int target, int[][] types) { int n = types.length; int MOD = 1_000_000_007; int[] dp = new int[target + 1]; dp[0] = 1; for (int[] type : types) { int count = type[0]; int marks = type[1]; int[] new_dp = new int[target + 1]; for (int j = 0; j <= target; j++) { // Ways from previous types (solving 0 of current type) long ways = dp[j]; // Ways by solving at least one of current type (cumulative sum) if (j >= marks) { ways = (ways + new_dp[j - marks]) % MOD; } // Remove overcounted cases (where > count questions were taken) if (j >= (count + 1) * marks) { ways = (ways - dp[j - (count + 1) * marks] + MOD) % MOD; } new_dp[j] = (int) ways; } dp = new_dp; } return dp[target]; }}Complexity
Time
O(n * target). The innermost loop is removed, leading to a quadratic time complexity which is a significant improvement.
Space
O(target). Similar to the previous approach, it uses two 1D arrays for the DP states.
Trade-offs
Pros
Highly efficient time complexity.
Optimal space complexity.
Cons
The recurrence relation is less intuitive and harder to derive than the brute-force approach.
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]; }}class Solution {public: int waysToReachTarget(int target, vector<vector<int>> &types) { int n = types.size(); const int mod = 1e9 + 7; int f[n + 1][target + 1]; memset(f, 0, sizeof(f)); 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]; }};class Solution: def waysToReachTarget(self, target: int, types: List[List[int]]) -> int: n = len(types) mod = 10 ** 9 + 7 f = [[0] * (target + 1) for _ in range(n + 1)] f[0][0] = 1 for i in range(1, n + 1): count, marks = types[i - 1] for j in range(target + 1): for k in range(count + 1): 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.