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.
Sample Input:
1 2 3Sample Output:
4 6 8Explanation for given Test Case :
Given A = 2, B = 4 and K = 2.
We can form below wands
4 = 2 + 2
6 = 4 + 2
8 = 4 + 4Approach :
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’.
Time Complexity : O(K * log(K))
Space Complexity : O(1)
