Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of ways to reach the given score.Examples:

Input: n = 20

Output: 4

There are following 4 ways to reach 20

(10, 10)

(5, 5, 10)

(5, 5, 5, 5)

(3, 3, 3, 3, 3, 5)This problem is a variation of coin change problem

Method 1 : With the help of DP and CoinChange code

Input: n = 20

Output: 4

There are following 4 ways to reach 20

(10, 10)

(5, 5, 10)

(5, 5, 5, 5)

(3, 3, 3, 3, 3, 5)This problem is a variation of coin change problem

Method 1 : With the help of DP and CoinChange code

int count( int S[], int m, int n ) { int i, j, x, y; // We need n+1 rows as the table is consturcted in bottom up manner using // the base case 0 value case (n = 0) int table[n+1][m]; // Fill the enteries for 0 value case (n = 0) for (i=0; i<m; i++) table[0][i] = 1; // Fill rest of the table enteries in bottom up manner for (i = 1; i < n+1; i++) { for (j = 0; j < m; j++) { // Count of solutions including S[j] x = (i-S[j] >= 0)? table[i - S[j]][j]: 0; // Count of solutions excluding S[j] y = (j >= 1)? table[i][j-1]: 0; // total count table[i][j] = x + y; } } return table[n][m-1]; }

Method 2 : The idea is to create a table of size n+1 to store counts of all scores from 0 to n. For every possible move (3, 5 and 10), increment values in table.

#include <stdio.h> int count(int n) { int table[n+1], i; memset(table, 0, sizeof(table)); table[0] = 1; for (i=3; i<=n; i++) table[i] += table[i-3]; for (i=5; i<=n; i++) table[i] += table[i-5]; for (i=10; i<=n; i++) table[i] += table[i-10]; return table[n]; }

You can also subscribe us for more interview questions :D

Please do share with us at admin@gohired.in , As sharing is caring