Skip to main content
Talentd

Form Largest Integer With Digits That Add up to Target - Solution & Explanation

HardArrayDynamic Programming15 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Dynamic Programming - Maximum Length

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Backtracking with Cost Iteration

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: Not applicable
Space Complexity: Not applicable

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).
Space Complexity: O(n) for the dp array.

Backtracking with Cost Iteration

Time Complexity: Not applicable
Space Complexity: Not applicable

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Cost IterationExponentialO(target)Good for understanding the search space or when constraints are very small
Dynamic Programming - Maximum LengthO(9 × target)O(target)Optimal approach for interviews and production solutions
DP with Greedy ReconstructionO(9 × target)O(target)When you need both optimal digit count and lexicographically largest result

Video Solution

Form Largest Integer With Digits That Add up to Target | Leetcode | Bi-weekly • Roshan Srivastava • 1,325 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Form Largest Integer With Digits That Add up to Target easy or hard?
The problem is classified as Hard because it combines dynamic programming with result reconstruction and lexicographical ordering. Many candidates find the DP state straightforward but struggle with building the final largest number correctly.
Form Largest Integer With Digits That Add up to Target Python/Java solution
Python and Java implementations typically build a DP array initialized with negative infinity except dp[0] = 0. After computing the maximum digit count for each cost, iterate digits from 9 to 1 and append digits that maintain dp[target] == dp[target - cost[d]] + 1. This constructs the largest valid number.
How to solve Form Largest Integer With Digits That Add up to Target in O(n)?
Treat the problem like an unbounded knapsack where digit costs are weights. Use a DP array dp[i] storing the maximum number of digits achievable for cost i. After filling the table in O(9 × target), reconstruct the answer by greedily selecting the largest digit that maintains the optimal DP value.
What is the best approach for Form Largest Integer With Digits That Add up to Target?
Dynamic programming with maximum digit length is the most effective approach. Compute dp[i] as the maximum number of digits that can produce cost i, then reconstruct the answer greedily from digit 9 to 1. This guarantees the numerically largest integer while keeping time complexity O(9 × target) and space O(target).
Is Form Largest Integer With Digits That Add up to Target asked at Google/Amazon/Meta?
Dynamic programming problems with knapsack-style transitions appear frequently in interviews at companies like Google, Amazon, and Meta. This specific problem tests DP state design, optimal reconstruction, and understanding of greedy ordering after DP.
What data structure is used in Form Largest Integer With Digits That Add up to Target?
The primary data structure is a one-dimensional dynamic programming array of size target + 1. The cost list for digits 1–9 is stored in a simple array. During reconstruction, a string or list is used to build the final integer.
What is the time complexity of Form Largest Integer With Digits That Add up to Target?
The optimal dynamic programming solution runs in O(9 × target) time because each DP state checks up to nine digits. Space complexity is O(target) for storing the DP array. Backtracking alternatives can become exponential because they explore many digit combinations.

Ready to solve this problem?

Practice Form Largest Integer With Digits That Add up to Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays