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.
This approach uses dynamic programming to determine the maximum length of the integer we can form for each cost value from 1 to the target. We maintain an array ‘dp’ where dp[j] represents the maximum number of digits we can form with cost j. By iterating through possible digits and attempting to update our dp array, we build up to the solution.
The C code uses an integer array dp to track the number of digits that can be formed for each cost up to the target. For each possible cost, we attempt to add each digit i+1 (0-indexed) and update the dp array if a larger number of digits can be formed. Finally, the result is constructed by taking the largest digits first that complete the target.
Time Complexity: O(n*m) where n is the target and m is the number of digits (9 in this case).
Space Complexity: O(n) for the dp array.
This approach uses a backtracking mechanism, attempting all possible combinations of digits. It attempts to form the largest integer by checking feasible combinations that sum to the target, ensuring the solution is constructed in descending order to ensure largeness.
C is limited in handling deep and varied recursion natively without risks of stack overflow and optimization issues for high constraint problems like this. It entails substantial manual management of memory and larger code size for similar backtracking.
Time Complexity: Not applicable
Space Complexity: Not applicable
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming - Maximum Length | Time Complexity: O(n*m) where n is the target and m is the number of digits (9 in this case). |
| Backtracking with Cost Iteration | Time Complexity: Not applicable |
| Default Approach | — |
| 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 |
Form Largest Integer With Digits That Add up to Target | Leetcode | Bi-weekly • Roshan Srivastava • 1,307 views views
Watch 8 more video solutions →Practice Form Largest Integer With Digits That Add up to Target with our built-in code editor and test cases.
Practice on FleetCode