Making Wands

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in companies
FacebookAdobeZoho Corporation

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 4 2
1 2 3
Sample Output 1:
4 6 8
3 4 5 6
Explanation For Sample Input 1:
Test Case 1 :  
Given A = 2, B = 4 and K = 2.
We can form below wands
4 = 2 + 2
6 = 4 + 2
8 = 4 + 4    

Test Case 2 : 
Given A = 1, B = 2 and K = 3.
We can form below wands
3 = 1 + 1 + 1
4 = 1 + 2 + 1
5 = 2 + 2 + 1
6 = 2 + 2 + 2
Sample Input 2:
2
4 5 2
2 2 2
Sample Output 2:
8 9 10
4
Hint

Try to find all combinations of wands.

Approaches (3)
Brute force

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

O(2 ^ K), where ‘K’ is the given number.

 

At each step, we are making two recursive calls and the depth of our recursive stack can go up to ‘K’. So, the time complexity will be O(2 ^ K).

Space Complexity

O(K), where ‘K’ is the given number.

 

The depth of our recursive stack can go up to ‘K’. So, the space complexity will be O(K).

Code Solution
(100% EXP penalty)
Making Wands
Full screen
Console