1449. Form Largest Integer With Digits - Target Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

The 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

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.

Python

def largestNumber(cost, target):
    dp = [-1] * (target + 1)
    dp[0] = 0
    for t in range(1, target + 1):
        for i in range(9):
            if t >= cost[i] and dp[t - cost[i]] != -1:
                dp[t] = max(dp[t], dp[t - cost[i]] + 1)

    if dp[target] == -1:
        return "0"

    res = []
    for d in range(8, -1, -1):
        while target >= cost[d] and dp[target] == dp[target - cost[d]] + 1:
            res.append(str(d + 1))
            target -= cost[d]
    return ''.join(res)

Java

import java.util.*;
class Solution {
    public String largestNumber(int[] cost, int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int t = 1; t <= target; ++t) {
            for (int i = 0; i < 9; ++i) {
                if (t >= cost[i] && dp[t - cost[i]] != -1) {
                    dp[t] = Math.max(dp[t], dp[t - cost[i]] + 1);
                }
            }
        }

        if (dp[target] == -1) return "0";

        StringBuilder sb = new StringBuilder();
        for (int d = 8; d >= 0; --d) {
            while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) {
                sb.append(d + 1);
                target -= cost[d];
            }
        }
        return sb.toString();
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string largestNumber(vector<int>& cost, int target) {
    vector<int> dp(target + 1, -1);
    dp[0] = 0;
    for (int t = 1; t <= target; ++t) {
        for (int i = 0; i < 9; ++i) {
            if (t >= cost[i] && dp[t - cost[i]] != -1) {
                dp[t] = max(dp[t], dp[t - cost[i]] + 1);
            }
        }
    }

    if (dp[target] == -1) return "0";

    string result;
    for (int d = 8; d >= 0; --d) {
        while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) {
            result += to_string(d + 1);
            target -= cost[d];
        }
    }
    return result;
}

JavaScript

function largestNumber(cost, target) {
    let dp = Array(target + 1).fill(-1);
    dp[0] = 0;
    
    for (let t = 1; t <= target; ++t) {
        for (let i = 0; i < 9; ++i) {
            if (t >= cost[i] && dp[t - cost[i]] !== -1) {
                dp[t] = Math.max(dp[t], dp[t - cost[i]] + 1);
            }
        }
    }
    
    if (dp[target] === -1) return "0";

    let result = '';
    for (let d = 8; d >= 0; --d) {
        while (target >= cost[d] && dp[target] === dp[target - cost[d]] + 1) {
            result += (d + 1).toString();
            target -= cost[d];
        }
    }
    return result;
}

#include <stdio.h>
#include <string.h>

char* largestNumber(int* cost, int costSize, int target) {
    static char result[5001];
    int dp[5001];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    
    for(int t = 1; t <= target; ++t) {
        for(int i = 0; i < 9; ++i) {
            if(t >= cost[i] && dp[t - cost[i]] != -1) {
                dp[t] = fmax(dp[t], dp[t - cost[i]] + 1);
            }
        }
    }
    
    if(dp[target] == -1) return "0";

    int idx = 0;
    for(int d = 8; d >= 0; --d) {
        while(target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) {
            result[idx++] = '1' + d;
            target -= cost[d];
        }
    }
    result[idx] = '\0';
    return result;
}

public class Solution {
    public string LargestNumber(int[] cost, int target) {
        int[] dp = new int[target + 1];
        Array.Fill(dp, -1);
        dp[0] = 0;
        for (int t = 1; t <= target; ++t) {
            for (int i = 0; i < 9; ++i) {
                if (t >= cost[i] && dp[t - cost[i]] != -1) {
                    dp[t] = Math.Max(dp[t], dp[t - cost[i]] + 1);
                }
            }
        }

        if (dp[target] == -1) return "0";

        StringBuilder sb = new StringBuilder();
        for (int d = 8; d >= 0; --d) {
            while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) {
                sb.Append(d + 1);
                target -= cost[d];
            }
        }
        return sb.ToString();
    }
}

This Python code follows the same logic as its counterparts in other languages. It utilizes a list to hold the maximum possible digits formable for each total cost from 0 to target. The outcome is constructed by adding digits from largest to smallest fulfilling the target cost.

Complexity

Time Complexity: O(n*m), where n is the target and m is the number of digits.
Space Complexity: O(n).

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.

Python

def largestNumber(cost, target):
    memo = {}
    def dfs(t):
        if t == 0:
            return ''
        if t < 0:
            return None
        if t in memo:
            return memo[t]

        best_result = None
        for i in range(9):
            result = dfs(t - cost[i])
            if result is not None:
                candidate = str(i + 1) + result
                if best_result is None or len(candidate) > len(best_result) or candidate > best_result:
                    best_result = candidate
        memo[t] = best_result
        return best_result

    res = dfs(target)
    return res if res is not None else "0"

Java

 /* Java is well-suited for backtracking but more cumbersome to manage compared to dynamic programming methods, making this approach less optimal. */

C++

/* Similar to C, backtracking in C++ for this scenario is less efficient compared to systemic dynamic programming solutions due to manual management complexities */

JavaScript

/* JavaScript solution for deep recursion in this problem non-trivial without engine or environment specifics that support extensive recursive operations optimally*/

/* C solution is not typically apt for recursive backtracking for this problem with simplicity and efficiency. Typically dynamic programming is the better fit here and in practice, we now focus on languages that handle recursion stack naturally like Python. */

/* C# can implement backtracking, but due to the potential depth and space concerns, it is not as straightforward compared to dynamic programming approaches or those optimized for simpler recursion, like Python. */

The Python backtracking approach uses a depth-first search with memoization. For each possible total cost, we check all digits' costs recursively and memoize results, tracking larger combinations. This approach, while feasible in Python due to native recursion and backtracking support, still requires careful management for efficiency.

Complexity

Time Complexity: Exponential in nature due to recursive exploration but pruned significantly by memoization.
Space Complexity: Can use O(n) in recursion stack depth and memo dictionary.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function largestNumber(cost: number[], target: number): string {
    const inf = 1 << 30;
    const f: number[][] = Array(10)
        .fill(0)
        .map(() => Array(target + 1).fill(-inf));
    const g: number[][] = Array(10)
        .fill(0)
        .map(() => Array(target + 1).fill(0));
    f[0][0] = 0;
    for (let i = 1; i <= 9; ++i) {
        const c = cost[i - 1];
        for (let 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';
    }
    const ans: number[] = [];
    for (let i = 9, j = target; i; ) {
        if (g[i][j] === j) {
            --i;
        } else {
            ans.push(i);
            j = g[i][j];
        }
    }
    return ans.join('');
}

func largestNumber(cost []int, target int) string {
	const inf = 1 << 30
	f := make([][]int, 10)
	g := make([][]int, 10)
	for i := range f {
		f[i] = make([]int, target+1)
		g[i] = make([]int, target+1)
		for j := range f[i] {
			f[i][j] = -inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= 9; i++ {
		c := cost[i-1]
		for 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"
	}
	ans := []byte{}
	for i, j := 9, target; i > 0; {
		if g[i][j] == j {
			i--
		} else {
			ans = append(ans, '0'+byte(i))
			j = g[i][j]
		}
	}
	return string(ans)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming - Maximum Length	Time Complexity: O(nm), where n is the target and m is the number of digits. Space Complexity:* O(n).
Backtracking with Cost Iteration	Time Complexity: Exponential in nature due to recursive exploration but pruned significantly by memoization. Space Complexity: Can use O(n) in recursion stack depth and memo dictionary.
Default Approach	–

Complexity analysis

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

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.

Form Largest Integer With Digits That Add up to Target solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming - Maximum Length

Approach 2: Backtracking with Cost Iteration

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Form Largest Integer With Digits That Add up to Target solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming - Maximum Length

Approach 2: Backtracking with Cost Iteration

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems