medium
0 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