# Form Largest Integer With Digits That Add up to Target **Difficulty:** HARD [External](https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target) Canonical: https://scaleengineer.com/dsa/problems/form-largest-integer-with-digits-that-add-up-to-target **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** Array --- ## Problem 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 **Example 2:** **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` # Approaches ## Top-Down Dynamic Programming with Memoization This approach solves the problem using recursion with memoization, which is a top-down dynamic programming technique. We define a function that finds the largest number for a given cost `t`. To prevent re-calculating results for the same cost, we store them in a memoization table. The function explores adding each possible digit and recursively solves for the remaining cost, always prioritizing choices that lead to a lexicographically larger final number. **Time:** O(target^2). There are O(target) subproblems to solve. For each subproblem `solve(t)`, we iterate through 9 digits. Inside the loop, string concatenation and comparison take time proportional to the string length, which can be up to O(t). This gives a total complexity of Σ(9 * t) for t from 1 to target, which is O(target^2). · **Space:** O(target^2). The recursion depth is O(target), and the memoization table `memo` stores O(target) entries. In the worst case, each entry can be a string of length O(target), leading to a total space complexity of O(target^2). **Pros:** Conceptually straightforward, as it directly models the recursive nature of the problem.; Guaranteed to find the optimal solution due to exhaustive search over possibilities. **Cons:** The time and space complexity of `O(target^2)` can be too slow and memory-intensive for large `target` values.; Frequent string concatenations and comparisons inside the recursion are inefficient.; Potential for stack overflow errors with deep recursion on very large `target` values, although constraints make this unlikely. ### Explanation The core of this method is a recursive function, let's call it `solve(t)`, which aims to find the largest number that can be formed with a total cost of `t`. To make the resulting number as large as possible, we must follow two principles: 1. The number should have as many digits as possible. 2. For two numbers with the same number of digits, the one that is lexicographically larger is preferred (e.g., "95" > "86"). Our recursive function `solve(t)` will try to append each digit from 9 down to 1. By trying larger digits first, we ensure that if we find multiple numbers of the same maximum length, we will construct the lexicographically largest one. The state of our recursion is the remaining cost `t`. The function will return the best string for that cost. - **Base Cases:** - If `t == 0`, we have met the target cost exactly. We return an empty string `""` to signify a valid end to the construction. - If `t < 0`, we have overshot the target, so this path is invalid. We return `null`. - **Memoization:** - We use an array `memo` where `memo[t]` stores the computed result for `solve(t)`. If `memo[t]` is already computed, we return it immediately. - **Recursive Step:** - We initialize a variable `best = null` to keep track of the best string for the current cost `t`. - We loop through digits `d` from 9 down to 1. - For each digit, we call `solve(t - cost[d-1])`. - If the recursive call returns a non-null result `subResult`, we form a new `candidate` string `d + subResult`. - We compare `candidate` with `best`. If `candidate` is larger (longer, or lexicographically greater for the same length), we update `best = candidate`. After checking all digits, we store `best` in `memo[t]` and return it. The final answer is `solve(target)`, or "0" if the result is `null`. ```java class Solution { String[] memo; int[] cost; public String largestNumber(int[] cost, int target) { this.cost = cost; memo = new String[target + 1]; String result = solve(target); return result == null ? "0" : result; } private String solve(int t) { if (t == 0) { return ""; } if (t < 0) { return null; } if (memo[t] != null) { // We use a special marker for computed but impossible states vs uncomputed states // For simplicity, if memo[t] is not null, it's computed. If it's a specific value like "IMPOSSIBLE", it's impossible. // Here, null itself serves as the impossible marker. return memo[t]; } String best = null; for (int d = 9; d >= 1; d--) { int c = cost[d - 1]; String subResult = solve(t - c); if (subResult != null) { String candidate = d + subResult; if (best == null || isLarger(candidate, best)) { best = candidate; } } } memo[t] = best; // Memoize the result (even if it's null) return best; } private boolean isLarger(String s1, String s2) { if (s1.length() != s2.length()) { return s1.length() > s2.length(); } return s1.compareTo(s2) > 0; } } ``` ### Algorithm - Define a recursive function `solve(t)` that returns the largest number string for a given remaining `target` cost `t`. - Use a memoization table (e.g., an array `memo`) to store the results of `solve(t)` to avoid redundant computations. - The base case for the recursion is `t == 0`, which returns an empty string `""` indicating a successful path. - If `t < 0`, it's an invalid path, so return a special marker like `null`. - In the recursive step for `solve(t)`, iterate through digits `d` from 9 down to 1. - For each digit `d`, make a recursive call `solve(t - cost[d-1])`. - If the subproblem returns a valid string, form a `candidate` string by prepending `d`. - Keep track of the best `candidate` found for `t` (one that is longer or lexicographically larger). - Store the best result in `memo[t]` before returning. - The initial call is `solve(target)`. If it returns `null`, no solution exists; otherwise, it's the answer. ## Bottom-Up Dynamic Programming with String Results This approach uses an iterative, bottom-up dynamic programming method. We build a DP table, `dp`, where `dp[t]` stores the largest number string that can be formed with a total cost of exactly `t`. We fill this table from `t=1` up to `target` by trying to extend previously computed optimal solutions for smaller costs. **Time:** O(target^2). We have two nested loops. The outer loop runs `target` times, and the inner loop runs 9 times. Inside the loops, string concatenation and comparison take O(target) time in the worst case. This leads to an overall time complexity of O(target * 9 * target) = O(target^2). · **Space:** O(target^2). The DP table `dp` stores O(target) strings, and each string can have a length of up to O(target). This results in O(target^2) space. **Pros:** Avoids recursion overhead and the risk of stack overflow.; The logic is a standard bottom-up DP formulation, which can be easier to reason about for some.; Guaranteed to find the optimal solution. **Cons:** The `O(target^2)` time and space complexity is inefficient for large `target` values.; Storing full strings in the DP table consumes a large amount of memory. ### Explanation This method avoids recursion by iteratively building up the solution from the smallest subproblems. We use a `String` array `dp` of size `target + 1`, where `dp[t]` will store the largest number whose digits' costs sum to `t`. 1. **Initialization**: We create the `dp` array. We can consider `dp[0]` to be an empty string `""`, representing that a cost of 0 is achieved with no digits. All other `dp[t]` are initially `null`, signifying that we haven't yet found a way to achieve cost `t`. 2. **Iteration**: We loop through each target cost `t` from 1 up to `target`. For each `t`, we want to find the best possible string. 3. **Transition**: To compute `dp[t]`, we consider all possible last digits we could have added. We iterate through each digit `d` from 1 to 9. Let its cost be `c = cost[d-1]`. If we can afford this digit (`t >= c`) and we have a valid solution for the remaining cost `t-c` (i.e., `dp[t-c]` is not `null`), we can form a new candidate number. The candidate is `d + dp[t-c]`. We compare this candidate with the current best string for `dp[t]`. A string is better if it's longer, or if it's lexicographically larger for the same length. We update `dp[t]` if we find a better candidate. 4. **Final Result**: After the loops complete, `dp[target]` will contain the largest number for the target cost. If `dp[target]` is still `null`, it means the target is unreachable, and we should return "0". ```java class Solution { public String largestNumber(int[] cost, int target) { String[] dp = new String[target + 1]; for (int t = 1; t <= target; t++) { for (int d = 1; d <= 9; d++) { int c = cost[d - 1]; if (t >= c) { String prevResult; if (t - c == 0) { prevResult = ""; } else { prevResult = dp[t - c]; } if (prevResult != null) { String candidate = d + prevResult; if (dp[t] == null || isLarger(candidate, dp[t])) { dp[t] = candidate; } } } } } return dp[target] == null ? "0" : dp[target]; } private boolean isLarger(String s1, String s2) { if (s1.length() != s2.length()) { return s1.length() > s2.length(); } return s1.compareTo(s2) > 0; } } ``` ### Algorithm - Create a DP array `dp` of size `target + 1`, where `dp[t]` will store the largest number string for cost `t`. - Initialize `dp[0]` to `""` and all other `dp[t]` to `null` (or a marker for unreachability). - Iterate through costs `t` from 1 to `target`. - For each `t`, iterate through digits `d` from 1 to 9. - Let `c` be the cost of digit `d`. If `t >= c` and the subproblem `dp[t-c]` has a valid solution, form a `candidate` string by prepending `d` to `dp[t-c]`. - Compare the `candidate` with the current `dp[t]`. If the candidate is larger (longer or lexicographically greater), update `dp[t]`. - After all iterations, `dp[target]` will hold the result. If it's `null`, return "0". ## Optimized Bottom-Up DP (Length-based, Two-Pass) This is the most efficient approach, which optimizes the dynamic programming solution by separating the problem into two phases. First, we use DP to find the maximum possible *length* of the number for each cost up to the target, without worrying about the actual digits. Second, using the length information from the first phase, we greedily construct the lexicographically largest number by choosing the largest possible digits from 9 down to 1 at each step. **Time:** O(target). Phase 1 takes O(target * 9) time. Phase 2 for reconstruction also takes O(target) time in the worst case, as `currentTarget` decreases in each step of appending a digit, and the total number of digits is at most O(target). · **Space:** O(target). The `dp` array for storing lengths requires O(target) space. The space for the result string is also at most O(target). **Pros:** Highly efficient with linear time and space complexity relative to `target`.; Avoids expensive string operations within the main DP computation, which is the primary bottleneck in other approaches. **Cons:** The two-phase approach can be slightly more complex to conceptualize and implement than a single-pass DP. ### Explanation This optimized method avoids the `O(target^2)` complexity of manipulating strings inside the DP loop. It works in two distinct passes. **Phase 1: Calculate Maximum Length** This phase is a classic Unbounded Knapsack-style problem. The goal is to find the maximum number of items (digits) that can fit into a knapsack of size `target` (cost). - We use an integer array `dp` of size `target + 1`, where `dp[t]` stores the maximum number of digits that sum to a cost of `t`. - We initialize `dp[0] = 0` and fill the rest of the array with a value like -1 to mark states as unreachable. - We iterate from `t = 1` to `target`. For each `t`, we try using each digit `d` (from 1 to 9). If we use a digit with cost `c`, the new length would be `1 + dp[t-c]`. We take the maximum over all possible digits. - The transition is: `dp[t] = max(dp[t], 1 + dp[t - cost[d-1]])`. - After this loop, `dp[target]` gives us the length of the largest possible number. If `dp[target]` is still -1, no solution exists. **Phase 2: Construct the Result String** Now that we know the maximum length, we can build the string. To make the number lexicographically maximal, we should use the largest digits (9, 8, 7...) as much as possible, from left to right. - We start with our `currentTarget` equal to the initial `target`. - We build the result string one digit at a time. For each digit, we iterate from `d = 9` down to `1`. - We select the first digit `d` that is a valid choice. A choice is valid if using it doesn't prevent us from achieving the maximum length. The check is: `currentTarget >= cost[d-1]` and `dp[currentTarget] == 1 + dp[currentTarget - cost[d-1]]`. - This check confirms that the state `currentTarget - cost[d-1]` is on an optimal path to `dp[0]`. - Once we find such a digit, we append it to our result, subtract its cost from `currentTarget`, and repeat the process to find the next digit. ```java import java.util.Arrays; class Solution { public String largestNumber(int[] cost, int target) { // Phase 1: Calculate max length for each cost int[] dp = new int[target + 1]; Arrays.fill(dp, -1); // Use -1 to indicate not reachable dp[0] = 0; for (int t = 1; t <= target; t++) { for (int i = 0; i < 9; i++) { int c = cost[i]; if (t >= c && dp[t - c] != -1) { dp[t] = Math.max(dp[t], 1 + dp[t - c]); } } } // If target is not reachable if (dp[target] < 0) { return "0"; } // Phase 2: Construct the result string greedily StringBuilder result = new StringBuilder(); int currentTarget = target; // We iterate from the largest digit (9) downwards for (int i = 8; i >= 0; i--) { int d = i + 1; int c = cost[i]; // Greedily append the largest possible digit as long as it's part of an optimal path while (currentTarget >= c && dp[currentTarget - c] != -1 && dp[currentTarget] == 1 + dp[currentTarget - c]) { result.append(d); currentTarget -= c; } } return result.toString(); } } ``` ### Algorithm - **Phase 1: Calculate Max Lengths** - Create an integer DP array `dp` of size `target + 1`. - `dp[t]` will store the maximum number of digits for a total cost of `t`. - Initialize `dp[0] = 0` and all other `dp[t]` to a value indicating unreachability (e.g., -1 or `Integer.MIN_VALUE`). - Iterate `t` from 1 to `target`. For each `t`, iterate through all digits `d` with cost `c`. - Update `dp[t]` using the transition: `dp[t] = max(dp[t], 1 + dp[t-c])`. - **Phase 2: Construct the Result** - If `dp[target]` is negative, return "0". - Initialize an empty `StringBuilder` for the result. - Start with `currentTarget = target`. - While `currentTarget > 0`: - Iterate through digits `d` from 9 down to 1. - Find the first digit `d` that satisfies the condition `dp[currentTarget] == 1 + dp[currentTarget - cost[d-1]]`. - This condition ensures that picking `d` keeps us on an optimal path to the maximum length. - Append `d` to the result, update `currentTarget -= cost[d-1]`, and break the inner loop to find the next digit. # Solutions ### Java ```java class Solution { public String largestNumber(int[] cost, int target) { final int inf = 1 << 30; int[][] f = new int[10][target + 1]; int[][] g = new int[10][target + 1]; for (var e : f) { Arrays.fill(e, -inf); } f[0][0] = 0; for (int i = 1; i <= 9; ++i) { int c = cost[i - 1]; for (int j = 0; j <= target; ++j) { if (j < c || f[i][j - c] + 1 < f[i - 1][j]) { f[i][j] = f[i - 1][j]; g[i][j] = j; } else { f[i][j] = f[i][j - c] + 1; g[i][j] = j - c; } } } if (f[9][target] < 0) { return "0"; } StringBuilder sb = new StringBuilder(); for (int i = 9, j = target; i > 0;) { if (j == g[i][j]) { --i; } else { sb.append(i); j = g[i][j]; } } return sb.toString(); } } ``` ### CPP ```cpp class Solution { public: string largestNumber(vector &cost, int target) { const int inf = 1 << 30; vector> f(10, vector(target + 1, -inf)); vector> g(10, vector(target + 1)); f[0][0] = 0; for (int i = 1; i <= 9; ++i) { int c = cost[i - 1]; for (int j = 0; j <= target; ++j) { if (j < c || f[i][j - c] + 1 < f[i - 1][j]) { f[i][j] = f[i - 1][j]; g[i][j] = j; } else { f[i][j] = f[i][j - c] + 1; g[i][j] = j - c; } } } if (f[9][target] < 0) { return "0"; } string ans; for (int i = 9, j = target; i;) { if (g[i][j] == j) { --i; } else { ans += '0' + i; j = g[i][j]; } } return ans; } }; ``` ### Python ```python class Solution: def largestNumber(self, cost: List[int], target: int) -> str: f = [[- inf] * (target + 1) for _ in range(10)] f[0][0] = 0 g = [[0] * (target + 1) for _ in range(10)] for i, c in enumerate(cost, 1): for j in range(target + 1): if j < c or f[i][j - c] + 1 < f[i - 1][j]: f[i][j] = f[i - 1][j] g[i][j] = j else: f[i][j] = f[i][j - c] + 1 g[i][j] = j - c if f[9][target] < 0: return "0" ans = [] i, j = 9, target while i: if j == g[i][j]: i -= 1 else: ans . append(str(i)) j = g[i][j] return "" . join(ans) ```