Number of Ways to Earn Points solution and explanation
9 more videos on this problem
Number of Ways to Earn Points || Dynamic Programming Knapsack || Leetcode-2585Aryan Mittal · 19:54 · 1K views
Number of Ways to Earn Points | Weekly Contest 335codingMohan · 10:41 · 736 views
Leetcode Weekly contest 335 - Hard - Number of Ways to Earn PointsPrakhar Agrawal · 10:27 · 593 views
【每日一题】LeetCode 2585. Number of Ways to Earn PointsHuifeng Guan · 13:47 · 559 views
2585. Number of Ways to Earn Points (Leetcode Hard)Programming Live with Larry · 11:25 · 504 views
Leetcode 2585 Number of Ways to Earn Points (Java) - Leetcode Weekly Contest 335 - Beats 100%TheAnalyticGuy · 18:50 · 251 views
2585. Number of Ways to Earn Points | Weekly Contest 335 | LeetCode | DCC NIT-ADCC NITA · 15:17 · 146 views
2585. Number of Ways to Earn Points || Hindi || Leetcode Weekly contest 335 5 March 2023CodeVed | Sanjib Asiwal · 14:44 · 108 views
[Leetcode Weekly 335] Number of Ways to Earn PointsSandeep Kumar · 20:09 · 99 views
leetcode 2585. Number of Ways to Earn Points - Dynamic ProgrammingCode-Yao · 13:46 · 80 views
The problem
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 = 6
Example 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: 5
Example 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
Approach overview
Problem Overview: You are given several question types where each type provides a fixed number of points and can be used a limited number of times. The goal is to count how many different combinations of questions reach exactly the target score. Order does not matter, so this becomes a bounded combination counting problem.
Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n * target * count), Space: O(n * target))
Treat the problem as a decision process across question types. At index i, decide how many questions of the current type to take (from 0 to count[i]). Each choice subtracts k * marks[i] from the remaining score and recursively processes the next type. Without caching, this creates many repeated subproblems. Memoization stores results for states defined by (index, remainingScore). This converts the exponential recursion into a polynomial solution. The approach is intuitive and mirrors the combinational search directly, which helps when reasoning about constraints and correctness.
This solution relies heavily on overlapping subproblems and is a classic application of dynamic programming. The input structure is stored in an array of types, and recursion iterates through each type while tracking the remaining score.
Approach 2: Dynamic Programming with State Compression (Bounded Knapsack) (Time: O(n * target * count), Space: O(target))
This problem maps directly to the bounded knapsack counting pattern. Let dp[s] represent the number of ways to reach score s. Initialize dp[0] = 1. For each question type, iterate scores from target down to 0. For every possible number of questions k from 1 to the allowed count, update dp[s] using dp[s - k * marks] if the score remains valid.
Iterating scores backward prevents reuse of the same question type more times than allowed. This effectively compresses the 2D DP state (type, score) into a single dimension. The memory usage drops to O(target), which is efficient for the constraint where the target score can be up to around 1000.
Recommended for interviews: The state-compressed dynamic programming solution is what interviewers typically expect. It demonstrates recognition of the bounded knapsack pattern and efficient space optimization. The recursive memoized version is still valuable during explanation because it clearly shows the decision structure before converting it into iterative DP.
Approach 1: Dynamic Programming with State Compression
This approach uses a dynamic programming (DP) technique to determine the number of different ways to achieve the target score. We use a 1D DP array where dp[j] represents the number of ways to achieve a score of j.
- Initialize an array
dpwithdp[0]set to 1 (one way to score zero points) and the rest to 0. - Iterate through each type of question, updating the DP array based on the number of questions of that type and the points they contribute.
- For each multiple of the mark for that type, adjust the scores up to the target.
This approach uses state compression to keep the memory usage low by maintaining only scores that are still reachable given the constraints.
MOD = 1000000007
def number_of_ways(target, types):
dp = [0] * (target + 1)
dp[0] = 1
for count, marks in types:
for t in range(target, -1, -1):
for c in range(1, count + 1):
if t - c * marks >= 0:
dp[t] = (dp[t] + dp[t - c * marks]) % MOD
return dp[target]
if __name__ == "__main__":
types = [[6, 1], [3, 2], [2, 3]]
print(number_of_ways(6, types))import java.util.Arrays;
public class NumberOfWays {
static final int MOD = 1000000007;
public static int numberOfWays(int target, int[][] types) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int[] type : types) {
int count = type[0], marks = type[1];
for (int t = target; t >= 0; t--) {
for (int c = 1; c <= count; c++) {
if (t - c * marks >= 0) {
dp[t] = (dp[t] + dp[t - c * marks]) % MOD;
}
}
}
}
return dp[target];
}
public static void main(String[] args) {
int[][] types = {{6, 1}, {3, 2}, {2, 3}};
System.out.println(numberOfWays(6, types));
}
}#include <vector>
#include <iostream>
#define MOD 1000000007
using namespace std;
int numberOfWays(int target, vector<vector<int>>& types) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (auto& type : types) {
int count = type[0], marks = type[1];
for (int t = target; t >= 0; t--) {
for (int c = 1; c <= count; c++) {
if (t - c * marks >= 0) {
dp[t] = (dp[t] + dp[t - c * marks]) % MOD;
}
}
}
}
return dp[target];
}
int main() {
vector<vector<int>> types = {{6, 1}, {3, 2}, {2, 3}};
int result = numberOfWays(6, types);
cout << result << endl;
return 0;
}const MOD = 1000000007;
function numberOfWays(target, types) {
const dp = Array(target + 1).fill(0);
dp[0] = 1;
types.forEach(([count, marks]) => {
for (let t = target; t >= 0; t--) {
for (let c = 1; c <= count; c++) {
if (t - c * marks >= 0) {
dp[t] = (dp[t] + dp[t - c * marks]) % MOD;
}
}
}
});
return dp[target];
}
console.log(numberOfWays(6, [[6, 1], [3, 2], [2, 3]]));#include <stdio.h>
#define MOD 1000000007
int numberOfWays(int target, int types[][2], int n) {
int dp[target+1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++) {
int count = types[i][0], marks = types[i][1];
for (int t = target; t >= 0; t--) {
for (int c = 1; c <= count; c++) {
if (t - c * marks >= 0) {
dp[t] = (dp[t] + dp[t - c * marks]) % MOD;
}
}
}
}
return dp[target];
}
int main() {
int types[][2] = {{6, 1}, {3, 2}, {2, 3}};
int result = numberOfWays(6, types, 3);
printf("%d\n", result);
return 0;
}using System;
public class NumberOfWays {
const int MOD = 1000000007;
public static int NumberOfWaysToEarnPoints(int target, int[][] types) {
int[] dp = new int[target + 1];
dp[0] = 1;
foreach (var type in types) {
int count = type[0], marks = type[1];
for (int t = target; t >= 0; t--) {
for (int c = 1; c <= count; c++) {
if (t - c * marks >= 0) {
dp[t] = (dp[t] + dp[t - c * marks]) % MOD;
}
}
}
}
return dp[target];
}
public static void Main() {
int[][] types = new int[][] {
new int[] {6, 1},
new int[] {3, 2},
new int[] {2, 3}
};
Console.WriteLine(NumberOfWaysToEarnPoints(6, types));
}
}Python implementation leverages a list to track the number of ways different scores can be achieved. Using loops, it updates the possible ways to reach every score by iterating over each question type and its corresponding properties.
Time Complexity: O(n * target * countmax)
Space Complexity: O(target), where countmax is the maximum count of questions of any type.
Approach 2: Recursive Dynamic Programming with Memoization
This approach utilizes recursion with memoization to explore all possible combinations of question types to achieve the target score. Each recursive call evaluates if it's possible to achieve the remaining score using the current and subsequent question types. Memoization is used to store results of subproblems to avoid re-computation.
- Define a recursive function to traverse each type of question and attempt to reach the target score.
- Use memoization to store the results of subproblems (e.g., how many ways to achieve a specific remaining score using given question types).
- Iteratively consider solving each number of questions of the current type.
from functools import lru_cache
MOD = 1000000007
def number_of_ways(target, types):
n = len(types)
@lru_cache(None)
def dp(remaining, index):
if remaining == 0:
return 1
if remaining < 0 or index == n:
return 0
count, marks = types[index]
ways = 0
for i in range(count + 1):
if remaining - i * marks >= 0:
ways = (ways + dp(remaining - i * marks, index + 1)) % MOD
return ways
return dp(target, 0)
if __name__ == "__main__":
types = [[6, 1], [3, 2], [2, 3]]
print(number_of_ways(6, types))import java.util.HashMap;
import java.util.Map;
public class NumberOfWaysMemoized {
static final int MOD = 1000000007;
public int numberOfWays(int target, int[][] types) {
Map<String, Integer> memo = new HashMap<>();
return dp(target, 0, types, memo);
}
private int dp(int remaining, int index, int[][] types, Map<String, Integer> memo) {
if (remaining == 0) return 1;
if (remaining < 0 || index == types.length) return 0;
String key = remaining + "," + index;
if (memo.containsKey(key)) return memo.get(key);
int count = types[index][0];
int marks = types[index][1];
int ways = 0;
for (int i = 0; i <= count; i++) {
if (remaining - i * marks >= 0) {
ways = (ways + dp(remaining - i * marks, index + 1, types, memo)) % MOD;
}
}
memo.put(key, ways);
return ways;
}
public static void main(String[] args) {
int[][] types = {{6, 1}, {3, 2}, {2, 3}};
NumberOfWaysMemoized solver = new NumberOfWaysMemoized();
System.out.println(solver.numberOfWays(6, types));
}
}In this Python solution, recursion with memoization is used to explore different scores. The dp() function considers each possible number of questions of a current type and recursively attempts to reach the target by calling itself with a decreased target and incremented index. Memoization efficiently caches computed results for quicker access.
Time Complexity: O(n * target * countmax) in the worst case, due to solving subproblems.
Space Complexity: O(n * target) due to recursion and memoization storage.
Approach 3: Dynamic Programming
We define f[i][j] to represent the number of methods to get j points exactly from the first i types of questions. Initially, f[0][0] = 1, and the rest f[i][j] = 0. The answer is f[n][target].
We can enumerate the ith type of questions, suppose the number of questions of this type is count, and the score is marks. Then we can get the following state transition equation:
$
f[i][j] = sum_{k=0}^{count} f[i-1][j-k times marks]
where k represents the number of questions of the ith type.
The final answer is f[n][target]. Note that the answer may be very large and needs to be modulo 10^9 + 7.
The time complexity is O(n times target times count) and the space complexity is O(n times target). n is the number of types of questions, and target and count$ are the target score and the number of questions of each type, respectively.
function waysToReachTarget(target: number, types: number[][]): number {
const n = types.length;
const mod = 10 ** 9 + 7;
const f: number[][] = Array.from({ length: n + 1 }, () => Array(target + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
const [count, marks] = types[i - 1];
for (let j = 0; j <= target; ++j) {
for (let 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];
}func waysToReachTarget(target int, types [][]int) int {
n := len(types)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, target+1)
}
f[0][0] = 1
const mod = 1e9 + 7
for i := 1; i <= n; i++ {
count, marks := types[i-1][0], types[i-1][1]
for j := 0; j <= target; j++ {
for 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]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Compression | Time Complexity: O(n * target * countmax) |
| Recursive Dynamic Programming with Memoization | Time Complexity: O(n * target * countmax) in the worst case, due to solving subproblems. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n * target * count) | O(n * target) | When reasoning about the problem recursively or explaining the state transition during interviews |
| Dynamic Programming with State Compression (Bounded Knapsack) | O(n * target * count) | O(target) | Preferred production and interview solution due to lower memory usage and clean iterative implementation |
Frequently asked questions
Is Number of Ways to Earn Points easy or hard?
Number of Ways to Earn Points is classified as a Hard problem because it combines bounded knapsack with combination counting. The challenge comes from handling limited quantities while avoiding overcounting and optimizing the DP state to keep memory manageable.
Number of Ways to Earn Points Python or Java solution
Both Python and Java implementations typically use the same bounded knapsack DP logic. A 1D array dp[target + 1] is updated for each question type while iterating scores backward. The algorithm remains O(n * target * count) with O(target) memory regardless of language.
What is the best approach for Number of Ways to Earn Points?
The most efficient approach is dynamic programming using the bounded knapsack pattern. Maintain a 1D DP array where dp[s] stores the number of ways to achieve score s. For each question type, iterate the target score backward and try taking the question 0 to count times. This runs in O(n * target * count) time and O(target) space.
Is Number of Ways to Earn Points asked at Google/Amazon/Meta?
Dynamic programming and knapsack-style counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of bounded knapsack, DP state transitions, and optimization using 1D state compression.
What data structure is used in Number of Ways to Earn Points?
The core data structure is a dynamic programming array. The question types are stored in an array where each entry contains the number of available questions and the points earned. The DP array tracks how many ways each score can be achieved.
What is the time complexity of Number of Ways to Earn Points?
The typical dynamic programming solution runs in O(n * target * count) time, where n is the number of question types and count is the maximum allowed usage per type. Each type iterates through the target score and tries all allowed quantities. Space complexity can be reduced to O(target) using state compression.
How to solve Number of Ways to Earn Points in O(n * target * count)?
Use a bounded knapsack dynamic programming approach. Initialize dp[0] = 1 and process each question type one by one. For every score from target down to 0, add contributions from using 1..count questions of that type. This counts all valid combinations without exceeding the allowed usage.