Largest Number From Fix Target

Moderate
0/80
profile
Contributed by
1 upvote
Asked in companies
IntuitShareChat

Problem statement

One day Mikasa went to “The Number Shop” where she wanted to buy some numbers. She has ‘N’ coins and for each number from 1 to 9, the cost is x1, x2,... x9, respectively. She wants to buy some numbers using exactly ‘N’ coins such that on concatenating these numbers she get the largest possible number. Help Mikasa to find the largest possible number.

If there is no way possible, print -1.

For Example : 
‘N’ = 5, cost: {2, 3, 1, 2, 4, 1, 5, 77, 4}

For the given example, the largest possible value that can be formed is 66666. As the cost of each 5 is 1 and we have a total of 5 coins. Hence the answer is 66666.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the total number of coins Mikasa has.

The second line of the test case contains 9 integers denoting the cost of every number from 1 to 9.
Output Format : 
For each test case, print a single integer denoting the largest possible number.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10    
1 <= N <= 1000
1 <= coins[i] <= 1000

Time limit: 1 sec
Sample Input 1 :
2
17
7 2 5 3 5 4 6 4 8
15
9 11 10 12 8 13 19 21 14
Sample Output 1 :
42222222
-1
Explanation For Sample Input 1 :
In the first test case, We can take seven 2’s and one 4 to make the total cost equal to 3 + 2 + 2 + 2 + 2 + 2 + 2 + 2 = 17. Hence the answer is 42222222. 

In the second test case, None of the combinations of coins can lead to the cost of 15. So Mikasa will not buy any number. Hence the answer is -1.
Sample Input 2 :
2
4
1 2 4 7 8 1 1 4 7 
3
7 4 8 1 9 6 2 1 7
Sample Output 2 :
7777
888
Hint

The approach is similar to the coin change problem, the only difference is the number could be very large, so we have to compare the strings.

Approaches (3)
Recursion

Approach: In this approach, we will calculate the maximum possible number we can make with every cost from 1 to ‘N’ using the given cost. As we are storing the final answer in a string we will have to compare all the strings formed using the current cost and return the maximum possible cost.

To do this, we will make another function ‘largetNumberHelper’ and we will pass an integer ‘N’ which represents the number of coins left after taking the ‘i’th number from 1 to 9 and the vector ‘cost’.


The steps are as follows:

  1. Take a string ‘ans’ to store the final answer.
  2. Call the function ‘largestNumberHelper’ and pass the integer ‘N’, the vector ‘cost’ as parameters.
  3. Return ‘ans’.

 

‘largestNumberHelper(N, cost)’:

  1. Check if ‘N’ is less than 0, then return ‘-1’, as the negative cost is not possible.
  2. Check if ‘N’ is equal to 0, return an empty string.
  3. Take a string ‘ans’ and initialize it with ‘-1’.
  4. Iterate through 1 to 9(say iterator be i):
    • Call the function ‘largestNumberHelper’ and pass the value ‘N’ - ‘cost[i - 1]’ and the cost array and store it in a string ‘res’, as we want to check if we can take the current number ‘i’ in the string or not.
    • Check if the value of ‘res’ is not ‘-1’, as that means that we can take the current number ‘i’ in the ‘ans’:
      • Check if ‘ans’ is ‘-1’:
        • Update ‘ans’ = ‘res’ + (char)(i + ‘0’).
      • Else:
        • Compare the two strings ‘res’ + (char)(i + ‘0’), ‘ans’ and update the larger string to ‘ans’.
  5. Return ‘ans’.
Time Complexity

O( 2 ^ N ), where ‘N’ is the total number of coins Mikasa has.

 

As we are going through all possible coin combinations and the total number of coins is ‘N’. Thus, either we can select them or we will not use them.

Hence the time complexity is O( 2 ^ N ).

Space Complexity

O( 1 )


No extra space is used.

Hence the space complexity is O(1)

Code Solution
(100% EXP penalty)
Largest Number From Fix Target
Full screen
Console