Form Largest Integer With Digits That Add up to Target

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".

Examples

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

Solution

Method 1 – Dynamic Programming (Maximize Digits)

Intuition

We want the largest integer, so we maximize the number of digits. For each possible cost, we try to build the largest number by choosing the highest digit possible at each step. We use DP to store the largest string for each cost.

Approach

1. Create a DP array where dp[t] is the largest string that can be formed with total cost t.
2. Initialize dp[0] as empty string.
3. For each cost from 1 to target, for each digit from 1 to 9:
   • If t - cost[digit-1] >= 0 and dp[t - cost[digit-1]] is not "0":
     • Form a candidate by appending the digit to dp[t - cost[digit-1]].
     • Keep the lexicographically largest string.
4. If dp[target] is empty, return "0".
5. Otherwise, return dp[target].

Code

C++

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<string> dp(target+1, "0");
        dp[0] = "";
        for (int t = 1; t <= target; ++t) {
            for (int d = 9; d >= 1; --d) {
                int c = cost[d-1];
                if (t-c >= 0 && dp[t-c] != "0") {
                    string cand = dp[t-c] + to_string(d);
                    if (cand.size() > dp[t].size() || (cand.size() == dp[t].size() && cand > dp[t]))
                        dp[t] = cand;
                }
            }
        }
        return dp[target] == "0" ? "0" : dp[target];
    }
};

Go

func largestNumber(cost []int, target int) string {
    dp := make([]string, target+1)
    for i := range dp {
        dp[i] = "0"
    }
    dp[0] = ""
    for t := 1; t <= target; t++ {
        for d := 9; d >= 1; d-- {
            c := cost[d-1]
            if t-c >= 0 && dp[t-c] != "0" {
                cand := dp[t-c] + strconv.Itoa(d)
                if len(cand) > len(dp[t]) || (len(cand) == len(dp[t]) && cand > dp[t]) {
                    dp[t] = cand
                }
            }
        }
    }
    if dp[target] == "0" {
        return "0"
    }
    return dp[target]
}

Java

class Solution {
    public String largestNumber(int[] cost, int target) {
        String[] dp = new String[target+1];
        Arrays.fill(dp, "0");
        dp[0] = "";
        for (int t = 1; t <= target; ++t) {
            for (int d = 9; d >= 1; --d) {
                int c = cost[d-1];
                if (t-c >= 0 && !dp[t-c].equals("0")) {
                    String cand = dp[t-c] + d;
                    if (cand.length() > dp[t].length() || (cand.length() == dp[t].length() && cand.compareTo(dp[t]) > 0))
                        dp[t] = cand;
                }
            }
        }
        return dp[target].equals("0") ? "0" : dp[target];
    }
}

Kotlin

class Solution {
    fun largestNumber(cost: IntArray, target: Int): String {
        val dp = Array(target+1) { "0" }
        dp[0] = ""
        for (t in 1..target) {
            for (d in 9 downTo 1) {
                val c = cost[d-1]
                if (t-c >= 0 && dp[t-c] != "0") {
                    val cand = dp[t-c] + d
                    if (cand.length > dp[t].length || (cand.length == dp[t].length && cand > dp[t]))
                        dp[t] = cand
                }
            }
        }
        return if (dp[target] == "0") "0" else dp[target]
    }
}

Python

class Solution:
    def largestNumber(self, cost: list[int], target: int) -> str:
        dp = ["0"] * (target+1)
        dp[0] = ""
        for t in range(1, target+1):
            for d in range(9, 0, -1):
                c = cost[d-1]
                if t-c >= 0 and dp[t-c] != "0":
                    cand = dp[t-c] + str(d)
                    if len(cand) > len(dp[t]) or (len(cand) == len(dp[t]) and cand > dp[t]):
                        dp[t] = cand
        return "0" if dp[target] == "0" else dp[target]

Rust

impl Solution {
    pub fn largest_number(cost: Vec<i32>, target: i32) -> String {
        let mut dp = vec!["0".to_string(); (target+1) as usize];
        dp[0] = "".to_string();
        for t in 1..=target {
            for d in (1..=9).rev() {
                let c = cost[(d-1) as usize];
                if t-c >= 0 && dp[(t-c) as usize] != "0" {
                    let cand = format!("{}{}", dp[(t-c) as usize], d);
                    if cand.len() > dp[t as usize].len() || (cand.len() == dp[t as usize].len() && cand > dp[t as usize]) {
                        dp[t as usize] = cand;
                    }
                }
            }
        }
        if dp[target as usize] == "0" { "0".to_string() } else { dp[target as usize].clone() }
    }
}

TypeScript

class Solution {
    largestNumber(cost: number[], target: number): string {
        const dp = Array(target+1).fill("0");
        dp[0] = "";
        for (let t = 1; t <= target; ++t) {
            for (let d = 9; d >= 1; --d) {
                const c = cost[d-1];
                if (t-c >= 0 && dp[t-c] !== "0") {
                    const cand = dp[t-c] + d;
                    if (cand.length > dp[t].length || (cand.length === dp[t].length && cand > dp[t]))
                        dp[t] = cand;
                }
            }
        }
        return dp[target] === "0" ? "0" : dp[target];
    }
}

Complexity

• ⏰ Time complexity: O(target * 9) — For each cost, we try all digits.
• 🧺 Space complexity: O(target * L) — For DP array, L is the max length of answer string.