1449. Form Largest Integer With Digits That Add up to Target LeetCode Solution
In this guide, you will get 1449. Form Largest Integer With Digits That Add up to Target LeetCode Solution with the best time and space complexity. The solution to Form Largest Integer With Digits That Add up to Target problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Form Largest Integer With Digits That Add up to Target
Given an array of integers cost and an integer target, return the maximum integer you can paint under the following rules:
The cost of painting a digit (i + 1) is given by cost[i] (0-indexed).
The total cost used must be equal to target.
The integer does not have 0 digits.
Since the answer may be very large, return it as a string. If there is no way to paint any integer given the condition, return “0”.
Example 1:
Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: “7772”
Explanation: The cost to paint the digit ‘7’ is 2, and the digit ‘2’ is 3. Then cost(“7772”) = 2*3+ 3*1 = 9. You could also paint “977”, but “7772” is the largest number.
Digit cost
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5
Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: “85”
Explanation: The cost to paint the digit ‘8’ is 7, and the digit ‘5’ is 5. Then cost(“85”) = 7 + 5 = 12.
Example 3:
Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: “0”
Explanation: It is impossible to paint any integer with total cost equal to target.
Constraints:
cost.length == 9
1 <= cost[i], target <= 5000
Complexity Analysis
Time Complexity: O(target)
Space Complexity: O(target)
1449. Form Largest Integer With Digits That Add up to Target LeetCode Solution in C++
class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
// dp[i] := the maximum length that cost i can achieve
vector<int> dp(target + 1, INT_MIN);
dp[0] = 0; // If cost = 0, the best choice is the empty string "".
for (int i = 1; i <= target; ++i)
for (int d = 0; d < 9; ++d)
if (i >= cost[d])
dp[i] = max(dp[i], dp[i - cost[d]] + 1);
if (dp[target] < 0)
return "0";
string ans;
// Greedily build the ans string.
for (int d = 8; d >= 0; --d)
while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) {
target -= cost[d];
ans += '1' + d;
}
return ans;
}
}; /* code provided by PROGIEZ */
1449. Form Largest Integer With Digits That Add up to Target LeetCode Solution in Java
class Solution {
public String largestNumber(int[] cost, int target) {
// dp[i] := the maximum length that cost i can achieve
int[] dp = new int[target + 1];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0; // If cost = 0, the best choice is the empty string "".
for (int i = 1; i <= target; ++i)
for (int d = 0; d < 9; ++d)
if (i >= cost[d])
dp[i] = Math.max(dp[i], dp[i - cost[d]] + 1);
if (dp[target] < 0)
return "0";
StringBuilder sb = new StringBuilder();
// Greedily build the ans string.
for (int d = 8; d >= 0; --d)
while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) {
target -= cost[d];
sb.append(1 + d);
}
return sb.toString();
}
} // code provided by PROGIEZ
1449. Form Largest Integer With Digits That Add up to Target LeetCode Solution in Python
