Form Largest Integer With Digits That Add up to Target

Hard
1066.

Form Largest Integer With Digits That Add up to Target

Form Largest Integer With Digits That Add up to Target is a hard coding problem on arrays, strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cost
 * @param {number} target
 * @return {string}
 */
var largestNumber = function(cost, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Form Largest Integer With Digits That Add up to Target Solution

Form Largest Integer With Digits That Add up to Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Form Largest Integer With Digits That Add up to Target is a hard coding problem on arrays, strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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

Hints for Form Largest Integer With Digits That Add up to Target

  1. Hint 1

    More digits always beats fewer, because every digit is at least 1 — so first maximise the length.

  2. Hint 2

    dp[t] = the most digits obtainable for exactly cost t; that is an unbounded knapsack.

  3. Hint 3

    Then build the answer greedily from digit 9 downwards, spending only where the length stays optimal.

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

  1. Fill dp[t] = max over d of dp[t - cost[d-1]] + 1, skipping unreachable predecessors.
  2. If dp[target] is unreachable, return "0".
  3. 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)

Java

public static String largestNumber(int[] cost, int target) {
    final int NEG = -1000000;
    int[] dp = new int[target + 1];
    Arrays.fill(dp, NEG);
    dp[0] = 0;
    for (int t = 1; t <= target; t++) {
        for (int d = 1; d <= 9; d++) {
            int c = cost[d - 1];
            if (t >= c && dp[t - c] >= 0) dp[t] = Math.max(dp[t], dp[t - c] + 1);
        }
    }
    if (dp[target] < 0) return "0";
    StringBuilder sb = new StringBuilder();
    int t = target;
    while (t > 0) {
        for (int d = 9; d >= 1; d--) {
            int c = cost[d - 1];
            if (t >= c && dp[t - c] == dp[t] - 1) {
                sb.append((char) ('0' + d));
                t -= c;
                break;
            }
        }
    }
    return sb.toString();
}

C++

string largestNumber(vector<int>& cost, int target) {
    const int NEG = -1000000;
    vector<int> dp(target + 1, NEG);
    dp[0] = 0;
    for (int t = 1; t <= target; t++) {
        for (int d = 1; d <= 9; d++) {
            int c = cost[d - 1];
            if (t >= c && dp[t - c] >= 0) dp[t] = max(dp[t], dp[t - c] + 1);
        }
    }
    if (dp[target] < 0) return "0";
    string out;
    int t = target;
    while (t > 0) {
        for (int d = 9; d >= 1; d--) {
            int c = cost[d - 1];
            if (t >= c && dp[t - c] == dp[t] - 1) {
                out += (char) ('0' + d);
                t -= c;
                break;
            }
        }
    }
    return 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings