We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Earn Points

Number: 2648

Difficulty: Hard

Paid? No

Companies: TuSimple

Problem Description

Given a test with n types of questions, where for each type you have a certain count of questions and each question of that type gives specific marks, determine the number of ways to score exactly a given target points. Questions of the same type are indistinguishable. Return the answer modulo 10^9 + 7.

Key Insights

  • This is a bounded knapsack (or coin change) style problem with limited supply for each type.
  • Use dynamic programming where dp[i] represents the number of ways to reach exactly i points.
  • For each question type, iterate over dp and update counts by considering solving 0, 1, ..., up to count questions of that type.
  • The answer is computed under modulo arithmetic due to the large size of possible outcomes.

Space and Time Complexity

Time Complexity: O(n * target * max_count)
Space Complexity: O(target)

Solution

We solve the problem using a dynamic programming approach. We initialize a dp array of size (target + 1) with dp[0] = 1 (base case: one way to accumulate 0 points). For each question type represented by [count, marks], update the dp array in reverse order (to avoid using updated states prematurely) by considering how many questions of that type we take (from 1 up to count) without exceeding the target. Each choice adds to the ways to achieve the current total score. This is effectively a bounded knapsack problem where we count the combinations rather than optimize a value. Finally, the computed dp[target] (modulo 10^9 + 7) gives the number of ways to score exactly the target points.

Code Solutions

# Python solution using dynamic programming

MOD = 10**9 + 7

def waysToReachTarget(target, types):
    # Initialize dp array where dp[i] is number of ways to reach i points
    dp = [0] * (target + 1)
    dp[0] = 1  # base case: one way to accumulate 0 points
    
    # Process each question type
    for count, marks in types:
        # Temporary dp array to store updated states after including current type
        new_dp = [0] * (target + 1)
        for points in range(target + 1):
            if dp[points]:
                # For each possible number of questions solved from current type
                for k in range(count + 1):
                    new_score = points + k * marks
                    if new_score > target:
                        break
                    new_dp[new_score] = (new_dp[new_score] + dp[points]) % MOD
        dp = new_dp
    return dp[target]

# Example usage:
target = 6
types = [[6,1],[3,2],[2,3]]
print(waysToReachTarget(target, types))  # Output: 7
← Back to All Questions