medium
6 views

Number of Ways to Reach Score

Calculate the number of distinct ways to reach a target score using moves of 3, 5, or 10 points.

Understand the Problem

Problem Statement

Consider a game where a player can score 3, 5, or 10 points in a move. Given an integer S representing the total score, find the number of distinct ways to reach exactly S points using any combination of these moves.

Order of moves does not matter; only the combination of move counts matters.

Constraints

  • 1 <= S <= 100000
  • Score S must be a non-negative integer
  • Player can use any number of moves (including zero of some types)
  • Only moves of 3, 5, or 10 points are allowed

Examples

Example 1
Input
20
Output
4
Explanation

There are 4 ways to reach score 20: 1. Two 10-point moves: 10 + 10 2. One 10-point and two 5-point moves: 5 + 5 + 10 3. Four 5-point moves: 5 + 5 + 5 + 5 4. Five 3-point moves and one 5-point move: 3 + 3 + 3 + 3 + 3 + 5

Example 2
Input
5
Output
1
Explanation

There is only 1 way to reach score 5: one 5-point move.

Example 3
Input
13
Output
2
Explanation

There are 2 ways to reach score 13: 1. One 10-point and one 3-point move: 10 + 3 2. Two 5-point and one 3-point move: 5 + 5 + 3

Solution

#include <stdio.h>

int countWays(int S) {
    int moves[] = {3, 5, 10};
    int dp[S + 1];
    
    // Initialize dp array
    for (int i = 0; i <= S; i++) {
        dp[i] = 0;
    }
    dp[0] = 1;  // One way to make score 0
    
    // For each move value
    for (int m = 0; m < 3; m++) {
        int move = moves[m];
        // Update all scores from move value to S
        for (int i = move; i <= S; i++) {
            dp[i] += dp[i - move];
        }
    }
    
    return dp[S];
}

int main() {
    int S;
    scanf("%d", &S);
    printf("%d\n", countWays(S));
    return 0;
}
Time:O(S) - We iterate through the score range once for each of the 3 move values
Space:O(S) - We maintain a dp array of size S+1
Approach:

C Solution Explanation:

  1. Declare function countWays that takes target score S as parameter
  2. Create moves array containing the three possible move values: {3, 5, 10}
  3. Initialize dp array of size S+1 with all zeros
  4. Set dp[0] = 1 representing one way to achieve score 0 (no moves)
  5. For each move value, iterate through scores from that move value up to S
  6. For each score i, add the ways to make (i - move_value) to dp[i]
  7. Read input S from stdin and print the result

The algorithm uses O(S) space and O(S) time complexity, making it efficient for the given constraints.

Visual Explanation

Loading diagram...
All Problems
Number of Ways to Reach Score | Letuscrack