Combination Sum

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
AmazonMorgan StanleySalesforce

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
1 1 0
Sample Output 1:
84
Explanation of sample input 1:
In the first test case, 
Combinations possible with X = 1, Y = 1 and Z = 0 are: [3, 4, 34, 43], and their sum is: 84
Sample Input 2:
2
1 1 1
0 1 1
Sample Output 2:
2940
108
Explanation of sample input 1:
In the first test case, 
Combinations possible with X = 1, Y = 1 and Z = 1 are: [3, 4, 5, 34, 43, 35, 53, 45, 54, 345, 354, 435, 453, 534, 543], and their sum is: 2940

In the second test case, 
Combinations possible with X = 0, Y = 1 and Z = 1 are: [4, 5, 45, 54], and their sum is: 108
Hint

Can you think of making all possible combinations of numbers having 3, 4 and 5 at most ‘X’, ‘Y’ and ‘Z’ times respectively?

Approaches (2)
Brute-Force.

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.
Time Complexity

O(X * Y * Z * log(X + Y + Z)), where ‘X’, ‘Y’ and ‘Z’ are the three numbers.

 

Since we are checking the digits of numbers ‘X’, ‘Y’ and ‘Z’ and using pow() function at each iteration so the overall time complexity will be O(X * Y * Z * log(X + Y + Z)).

Space Complexity

O(1).

 

Constant extra space is required.

Code Solution
(100% EXP penalty)
Combination Sum
Full screen
Console