Last Updated: 6 Mar, 2021
Combination Sum
Hard
Asked in companies
You have been given three numbers ‘X’, ’Y’ and ‘Z’. You have to find the sum of all the numbers formed by the combination of the digits 3, 4 and 5. You can use 3 at most ‘X’ times, 4 at most ‘Y’ times, and 5 at most ‘Z’ times as a digit in numbers.
Note:
Output the sum modulo 10 ^ 9 + 7.
For example :
If ‘X’ = 1, ‘Y’ = 1 and ‘Z’ = 0 then the output will be 84.
Explanation : 3 + 4 + 34 + 43 = 84
Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first and only line of each test case contains three space-separated integers denoting ‘X’, ‘Y’, and ‘Z’ respectively.
Output Format:
For each test case, print a single line containing the sum of all the numbers formed by having 3 at most ‘X’ times, having 4 at most ‘Y’ times, and having 5 at most ‘Z’ times as a digit.
The output of each test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
0 <= X, Y, Z <= 10
Where ‘T’ is the number of test cases and ‘X’, ‘Y’ and ‘Z’ are the three integers.
Time limit: 1 sec.
Approaches
The basic idea is to make all possible combinations of numbers having ‘X’ 3s, ‘Y’ 4s and ‘Z’ 5s as digits and adding them to get the desired result.
- Make an array let’s say “fact” that will contain the value of the factorials of the indices.
- Make a “sum” variable that will contain the sum of different combinations.
- Run three nested loops to find different combinations of i 3’s, j 4’s and k 5’s where i < X, j < Y and k < Z.
- Take an integer ‘t’ that will contain the sum of ‘i’, ‘j’ and ‘k’(all combinations considered).
- If ‘t’ is 0, it means that we don’t have any valid combination so we will move on to the next step.
- At every iteration, if ‘i’ > 0, increment “sum” by the value (3 * (pow(10, t) - 1) * (fact[t - 1])) / (9 * fact[i - 1] * fact[j] * fact[k]).
- For example, if ‘X’ is 2, the above formula will give as 3 + 33 due to the formula (3 * (pow(10, t) - 1) / 9).
- By the above formula, we will get the sum of all occurrences of 3 at unit place,decimal place and so on.
- Do the same for ‘j’ and ‘k’ i.e 3 and 5.
- After different combinations of ‘i’, ‘j’ and ‘k’, return “sum” modulo 10^9 + 7.
In this approach we will be using Dynamic programming. We will find all combinations of numbers having exactly X - 3’s, Y - 4’s and Z - 5’s, and then add them to get our desired sum.
For this, we will create two 3D-DP arrays, let’s say “num[N][N][N]”, “sum[N][N][N]”, where ‘N’ is the maximum possible value of ‘X’, ‘Y’ and ‘Z’:
- “Sum[][][]”, will store the sum, while “num[][][]”, will store the numbers solved.
- We will now add values into the DP arrays. For this, we will be using the previously computed values. So, we will be needing a base value or initialising value for the array. We will initialize the “num[0][0][0]” as 1, because if we use 3, 4 and 5 0 times each then we will have only one possible number, i.e 0.
- Now, for the sum array we can find “sum[i][j][k]”, we will use the following formula:
sum[i][j][k] = 10 * (sum[i - 1][j][k] + sum[i][j - 1][k] + sum[i][j][k - 1])
+ 3 * num[i - 1][j][k]
+ 4 * num[i][j - 1][k]
+ 5 * num[i][j][k - 1]
- Finally we will add the modulus of sum stored at this index in a variable “ans”, that will store our final sum.
- Return “sum” mod 1000000007