I was doing a coding test (already finished, so no cheating for me) and came across this problem, which I'll describe in few steps:
- We have a keypad, like on cellphones, with keys from 1 to 9, where 1 is the space key (" ")
- We are given a message to convert to numbers based on the "distance" of each letter (P = 7, S = 7777, K = 55, ...), for example DRSA becomes 377777772
- Now we need to calculate the the number of the possible messages we could write with that same number (DPPPPPPPA, DPPPPPQA, ...)
The method I came up with is the following:
- I split the number by its different digits obtaining for example 3, 7777777, 2
- I ignored single digits as they do not add "value" to the permutations (as far as I understood it)
- I take each section of digits and based on its length (in this case 7 digits) I calculate every possible permutation and count them
Now this method works, but it's slow so I wanted to find a way to calculate the number of these permutations without counting them manually.
I found out about integer compositions, which in my case should have a maximum value. In this case the key 7 has a maximum value of 4 so its composition would be something like this:
- 4+3
- 3+4
- 4+1+2
- 4+2+1
- 1+2+4
- 1+4+2
- ...
How can I limit the maximum value of the composition (4) of a number (7)? How can I know the number of elements in it?