Watch 9 video solutions for Form Largest Integer With Digits That Add up to Target, a hard level problem involving Array, Dynamic Programming. This walkthrough by Roshan Srivastava has 1,307 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of integers cost and an integer target, return the maximum integer you can paint under the following rules:
(i + 1) is given by cost[i] (0-indexed).target.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 == 91 <= cost[i], target <= 5000Problem Overview: You are given the cost of digits 1–9 and a target value. The goal is to construct the numerically largest integer such that the total cost of its digits equals the target. Digits can be reused any number of times, but the final result must be the largest possible integer (more digits first, then lexicographically larger digits).
Approach 1: Backtracking with Cost Iteration (Exponential time, O(target) space)
This approach tries all combinations of digits whose costs sum to the target using backtracking. You recursively pick digits from 9 down to 1, subtract their cost, and continue exploring until the remaining cost reaches zero. Valid candidates are compared by length first and lexicographical order second to track the best result. The search tree grows quickly because each step may branch into up to nine choices, giving exponential time complexity. This method is useful for understanding the problem structure but becomes impractical for larger targets.
Approach 2: Dynamic Programming - Maximum Length (O(9 × target) time, O(target) space)
The optimal solution uses dynamic programming to maximize the number of digits that can reach a given cost. Create a DP array dp[i] representing the maximum digit count that forms total cost i. For each cost from 1 to target, iterate through digits 1–9 and update dp[i] if using that digit improves the length. The key insight: a larger integer always has more digits, so maximizing digit count guarantees the largest result.
After computing the DP table, reconstruct the number greedily. Start from digit 9 down to 1 and check whether adding that digit keeps the DP optimal (dp[target] == dp[target - cost[d]] + 1). If true, append that digit and reduce the target. This reconstruction ensures the final integer is lexicographically largest while preserving the optimal digit count.
The DP only stores states up to target, making the complexity linear in the target multiplied by the 9 digits. The cost array behaves like a bounded array lookup, so transitions are constant time.
Recommended for interviews: The dynamic programming approach with maximum-length tracking is what interviewers expect. Backtracking shows you understand the search space, but the DP solution demonstrates optimization skills and knowledge of unbounded knapsack-style transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Cost Iteration | Exponential | O(target) | Good for understanding the search space or when constraints are very small |
| Dynamic Programming - Maximum Length | O(9 × target) | O(target) | Optimal approach for interviews and production solutions |
| DP with Greedy Reconstruction | O(9 × target) | O(target) | When you need both optimal digit count and lexicographically largest result |