Largest Number From Fix Target

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

In this approach, we will not only calculate the maximum possible number we can make with every cost from 1 to ‘N’ using the given cost but will also store them in an array ‘dp’. By doing so, we will be able to skip many precomputed cases, hence reducing the time complexity.

The steps are as follows:

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

‘largestNumberHelper(N, cost, dp)’:

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. Check if ‘dp[N]’ is not equal to -1, which means that the current value is already computed by us:
   1. Return ‘dp[N]’.
4. Take a string ‘ans’ and initialize it with ‘-1’.
5. 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’.
6. Update ‘dp[N]’ = ‘ans’.
7. Return ‘ans’.

In this approach, we will iterate through the arrays ‘coins’, and for each coin, we will calculate the maximum number possible which we can make from all the coins from 1 to 9 and if we found a coin having cost less than or equal to the current coins we are taking we will update the maximum of the two strings we have, i.e. the previous string ‘dp[j]’ and the new string which will be (char)(i + ‘0’) + ‘dp[j - cost[i]]’

The steps are as follows: 

1. Take a vector of string ‘dp’ to store the maximum possible number and initialize it with “-1”.
2. Update ‘dp[0]’ = “0”.
3. Iterate through the loop from 1 to 9(say iterator be i):
   • Iterate through the loop from ‘cost[i]’ to ‘N’(say iterator be j):
     • Check if ‘dp[j - cost[i]] != “-1”):
       • Compare the two strings (char)(i + ‘0’) + ‘dp[j - cost[i]]’, ‘dp[j]’ and update the larger string to ‘dp[j]’.
4. Return ‘dp[N]’.