Last Updated: 24 Feb, 2021
Making Wands
Moderate
Asked in companies
Harry Potter came to Olivander to buy magic wands for his son Albus.
Olivander has only two kinds of wands, one is of power ‘A’ and the other is of power ‘B’. He has an infinite supply of these two kinds of wands.
Albus wants to see wands of different powers, so Harry did magic and did the following things.
Harry chooses zero or more wands of power ‘A’ and zero or more wands of power ‘B’. He chose exactly ‘K’ wands.
Then Harry adds the power of all ‘K’ wands and made a new wand of power equal to the sum of powers of ‘K’ chosen wands.
Albus asked Harry to show all possible unique wands. Two wands are considered to be unique if they have different powers.
Harry is getting late for his meeting at the Ministry of Magic. So, he called you for help.
Input Format
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains three space-separated integers ‘A’, ‘B’, and ‘K’.
Output Format:
For each test case, print the powers of all unique wands in sorted order separated by a single space.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= K <= 5000
0 <= A, B <= 10 ^ 5
Time Limit: 1sec
Approaches
The idea here is to generate all possible combinations of wands. At each step, we have two choices either combine a wand of power ‘A’ or combine a wand power ‘B’. So, we will solve this problem recursively by making two recursive calls at each step, one for power ‘A’ and other for power ‘B’.
Algorithm:
- Declare an array to store all unique wands say, ‘answer’. Also declare a hash set say, ’hashSet’ to keep track of duplicate wands.
- Call ‘doRecursive’ function to store all unique wands in ‘answer’ array.
- Sort the ‘answer’ array.
- Finally, return the ‘answer’.
Description of ‘doRecursive’ function.
This function is used to generate all possible combinations of wands.
This function will take six parameters.
- A: An integer denoting the power of wand of type ‘A’.
- B: An integer denoting the power of wand of type ‘B’.
- current: An integer denoting the power of the current combination of the wand.
- K: An integer that denotes the number of wands that are left in the current recursive call.
- answer: An array to store all unique wands.
- hashSet: An hash set to keep track of duplicate wands.
doRecursive(A, B, current, K, answer, hashSet):
- If ‘K’ equals 0 then if ‘current’ is not present in the ‘hashSet’ then add ‘current’ to ‘answer’ and ‘hashSet’ and break the recursion as we have used maximum allowed wands.
- Add ‘A’ to current and recursively the function by decrementing value of ‘K’ i.e. call ‘doRecursive(A, B, current + A, K - 1, answer, hashSet)’.
- Add ‘B’ to current and recursively the function by decrementing value of ‘K’ i.e. call ‘doRecursive(A, B, current + B, K - 1, answer, hashSet)’.
The idea here is to use that the previous approach as overlapping subproblems property. So we can use dynamic programming to avoid repetitive computation.
Example :
The subproblems marked in orange color are overlapping subproblems so we will use dynamic programming to store them.
Algorithm:
- Declare an array to store all unique wands say, ‘answer’. Also declare a hash set say, ’hashSet’ to keep track of duplicate wands.
- Declare a ‘dp’ hash set to check whether we have calculated this subproblem or not.
- Call ‘doRecursive’ function to store all unique wands in ‘answer’ array.
- Sort the ‘answer’ array.
- Finally, return the ‘answer’.
Description of ‘doRecursive’ function.
This function is used to generate all possible combinations of wands.
This function will take seven parameters.
- A: An integer denoting the power of wand of type ‘A’.
- B: An integer denoting the power of wand of type ‘B’.
- current: An integer denoting the power of the current combination of the wand.
- K: An integer that denotes the number of wands that are left in the current recursive call.
- answer: An array to store all unique wands.
- hashSet: An hash set to keep track of duplicate wands.
- dp: An ‘dp’ hash set to check whether we have calculated a current subproblem or not.
doRecursive(A, B, current, K, answer, hashSet):
- If ‘K’ equals 0 then if ‘current’ is not present in the ‘hashSet’ then add ‘current’ to ‘answer’ and ‘hashSet’ and break the recursion as we have used maximum allowed wands.
- If (K, current) is present in ‘dp’ hash set then break the recursion as we have already calculated ‘answer’ for this subproblem then going through this path will not give us a wand unique power.
- Add ‘A’ to current and recursively the function by decrementing value of ‘K’ i.e. call ‘doRecursive(A, B, current + A, K - 1, answer, hashSet)’.
- Add ‘B’ to current and recursively the function by decrementing value of ‘K’ i.e. call ‘doRecursive(A, B, current + B, K - 1, answer, hashSet)’.
- Store (K, current) in ‘dp’ hash set.
The idea here is to generate all possible combinations of wands. We will run a loop from i = 0 to K. Then we can make a combination by taking wand of power equals (‘A’ * i) times and wand of power equals (‘B’ * ‘K – i’ ) times. We will use a hash set to keep track of duplicate combinations.
Algorithm:
- Declare an array to store all unique wands say, ‘answer’. Also declare a hash set say, ’hashSet’ to keep track of duplicate wands.
- Run a loop from i = 0 to ’K’.
- Say power of the current combination of wands = ‘current’ = A * i + ( K – i ) * B.
- If ‘current’ is not present in ‘hashSet’ then add ‘current’ to the answer.
- Add ‘current’ to ‘hashSet’.
- Sort the ‘answer’ array.
- Finally, return the ‘answer’.
Similar problems