Form Largest Integer With Digits That Add up to Target — Hard Problem & Solution

Painting digit d (from 1 to 9) costs cost[d - 1]. Build the largest integer whose digits' total painting cost is exactly target.

Difficulty: Hard
Topics: Arrays, Strings, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Painting digit d (from 1 to 9) costs cost[d - 1]. Build the largest integer whose digits' total painting cost is exactly target.

The result may not contain the digit 0. Return it as a string, or "0" if no integer can be formed.

Example 1

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: 7772
Explanation: Costs 2 + 2 + 2 + 3 = 9; four digits beat any three-digit number.

Example 2

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: 85
Explanation: Two digits are the most affordable, and `85` is the largest such pair.

Example 3

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: 0
Explanation: Every cost is even, so an odd target is unreachable.

Constraints

cost.length == 9
1 <= cost[i], target <= 5000

How to solve Form Largest Integer With Digits That Add up to Target

Two phases. First an unbounded knapsack: dp[t] is the maximum number of digits costing exactly t, with dp[0] = 0 and everything else unreachable until proven otherwise. Then reconstruct greedily — at each step take the largest digit d for which dp[t - cost[d-1]] == dp[t] - 1, which keeps the length maximal while making each position as large as possible.

Approach

Fill dp[t] = max over d of dp[t - cost[d-1]] + 1, skipping unreachable predecessors.
If dp[target] is unreachable, return "0".
Set t = target and repeatedly append the largest d whose predecessor state has exactly one fewer digit, subtracting its cost.

Why it works

Length dominates value because no leading zeros are possible — a 4-digit number always beats a 3-digit one whatever the digits. Once the length is fixed, the greedy is safe precisely because the dp[t - c] == dp[t] - 1 test guarantees the remaining budget still admits the full remaining length, so taking the biggest digit now costs nothing later.

Complexity

Time — O(9 · target)
Space — O(target)

Pitfalls

Maximising the digit sum or the value directly both give wrong answers; length comes first.
The cost must be spent exactly, not merely not exceeded.
An unreachable target returns the string "0", not an empty string.

Reference solution

Python

from typing import List

def largestNumber(cost: List[int], target: int) -> str:
    NEG = -10**6
    dp = [NEG] * (target + 1)
    dp[0] = 0
    for t in range(1, target + 1):
        for d in range(1, 10):
            c = cost[d - 1]
            if t >= c and dp[t - c] >= 0:
                dp[t] = max(dp[t], dp[t - c] + 1)
    if dp[target] < 0:
        return "0"
    out = []
    t = target
    while t > 0:
        for d in range(9, 0, -1):
            c = cost[d - 1]
            if t >= c and dp[t - c] == dp[t] - 1:
                out.append(str(d))
                t -= c
                break
    return "".join(out)

JavaScript

var largestNumber = function(cost, target) {
    var NEG = -1000000, t, d;
    var dp = [];
    for (t = 0; t <= target; t++) dp.push(NEG);
    dp[0] = 0;
    for (t = 1; t <= target; t++) {
        for (d = 1; d <= 9; d++) {
            var c = cost[d - 1];
            if (t >= c && dp[t - c] >= 0 && dp[t - c] + 1 > dp[t]) dp[t] = dp[t - c] + 1;
        }
    }
    if (dp[target] < 0) return "0";
    var out = "";
    t = target;
    while (t > 0) {
        for (d = 9; d >= 1; d--) {
            var cc = cost[d - 1];
            if (t >= cc && dp[t - cc] === dp[t] - 1) {
                out += String(d);
                t -= cc;
                break;
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue