Saurabh Kumar

Posted on

# Misc: Possible Ways to Add

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

## Problem

A very interesting and fairly easy question which I found during one interview was:

A batsman can score either {1,2,3} runs in a ball. Find the number of ways he can score "X".

Other variants - Given possible coins 2, 3, 5 - how many ways can result in a sum of 43

If you got stuck thinking or applying permutations and then visualizing it in code - just look at this simple code

## Solution

``````    static int possibleWaysToReachScore(List<Integer> runs, int x) {

// table[i] will store count of solutions for value i.
int[] table = new int[x + 1];

// Initialize all table values as 0
Arrays.fill(table, 0);

// Base case (If given value is 0)
table[0] = 1;

// One by one consider given runs
// and update the table[]
// values after the index greater
// than or equal to the value of
// the picked move
runs.forEach(
n -> IntStream.rangeClosed(n, x)
.forEach(i -> table[i] += table[i - n])
);

return table[x];
}
``````

## Explanation:

• given we have 1,2,3 and we want say 10 runs, we start with a dp array which will store all possible ways to get to the index (which represents the runs).
so, naturally `table[0]=1`

• iteration for n = 1

• loop from 1 -> 10 and sum `i + (i-1)`
• table[1] = table[1]+table[0] = 1
• table[2] = table[2]+table[1] = 1 and so on...
• table[10] = table[10]+table[9] = 1
• iteration for n = 2

• loop from 2 -> 10 and sum `i + (i-2)`
• table[2] = table[2]+table[0] = 1+1 = 2
• table[3] = table[3]+table[1] = 1+1 = 2
• table[4] = table[4]+table[2] = 1+2 = 3, 3
• table[6] = table[6]+table[4] = 1+3 = 4, 4
• table[8] = table[8]+table[6] = 1+4 = 5, 5
• table[10] = table[10]+table[8] = 1+5 = 6
• iteration for n = 3

• loop from 3 -> 10 and sum `i + (i-3)`
• table[3] = table[3]+table[0] = 2+1 = 3
• table[4] = table[4]+table[1] = 3+1 = 4
• table[7] = table[7]+table[4] = 4+4 = 8
• table[10] = table[10]+table[7] = 6+8 = 14

then we loop over the range n (the current score possible till required score)

in the end we will have a dp containing all ways to reach any number till X
`[(0=1), (1=1), (2=2), 3, 4, 5, (6=7), 8, 10, (9=12), 14]`

of course, another variant of the same problem is Given possible scores a batsman can score in one ball is {1, 2, 3}, how many ways can he score X runs in B balls - that is a tough one to explain!

but here's the solution nonetheless!
GeeksForGeeks