2585. Number of Ways to Earn Points LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2585. Number of Ways to Earn Points LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Earn Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Ways to Earn Points solution in C++
Number of Ways to Earn Points solution in Java
Number of Ways to Earn Points solution in Python
Additional Resources

2585. Number of Ways to Earn Points LeetCode Solution image

Problem Statement of Number of Ways to Earn Points

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 3 questions of the same type, then solving the 1st and 2nd questions is the same as solving the 1st and 3rd questions, or the 2nd and 3rd questions.

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 <= 1000
n == types.length
1 <= n <= 50
types[i].length == 2
1 <= counti, marksi <= 50

Complexity Analysis

Time Complexity: O(n \cdot \texttt{target} \cdot \texttt{count})
Space Complexity: O(n \cdot \texttt{target})

2585. Number of Ways to Earn Points LeetCode Solution in C++

class Solution {
 public:
  int waysToReachTarget(int target, vector<vector<int>>& types) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j] := the number of ways to earn j points with the first i types
    vector<vector<int>> dp(types.size() + 1, vector<int>(target + 1));
    dp[0][0] = 1;

    for (int i = 1; i <= types.size(); ++i) {
      const int count = types[i - 1][0];
      const int mark = types[i - 1][1];
      for (int j = 0; j <= target; ++j)
        for (int solved = 0; solved <= count; ++solved)
          if (j - solved * mark >= 0) {
            dp[i][j] += dp[i - 1][j - solved * mark];
            dp[i][j] %= kMod;
          }
    }

    return dp[types.size()][target];
  }
};
/* code provided by PROGIEZ */

2585. Number of Ways to Earn Points LeetCode Solution in Java

class Solution {
  public int waysToReachTarget(int target, int[][] types) {
    final int kMod = 1_000_000_007;
    // dp[i][j] := the number of ways to earn j points with the first i types
    int[][] dp = new int[types.length + 1][target + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= types.length; ++i) {
      final int count = types[i - 1][0];
      final int mark = types[i - 1][1];
      for (int j = 0; j <= target; ++j)
        for (int solved = 0; solved <= count; ++solved)
          if (j - solved * mark >= 0) {
            dp[i][j] += dp[i - 1][j - solved * mark];
            dp[i][j] %= kMod;
          }
    }

    return dp[types.length][target];
  }
}
// code provided by PROGIEZ

2585. Number of Ways to Earn Points LeetCode Solution in Python

class Solution:
  def waysToReachTarget(self, target: int, types: list[list[int]]) -> int:
    kMod = 1_000_000_007
    # dp[i][j] := the number of ways to earn j points with the first i types
    dp = [[0] * (target + 1) for _ in range(len(types) + 1)]
    dp[0][0] = 1

    for i in range(1, len(types) + 1):
      count = types[i - 1][0]
      mark = types[i - 1][1]
      for j in range(target + 1):
        for solved in range(count + 1):
          if j - solved * mark >= 0:
            dp[i][j] += dp[i - 1][j - solved * mark]
            dp[i][j] %= kMod

    return dp[len(types)][target]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents