Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 24 Feb, 2021

Making Wands

Moderate
Asked in companies
GoogleAdobeFacebook

Problem statement

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

01 Approach

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)’.