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#
1
2
3
4
5
6
7
8
9
10
11
12
13
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#
1
2
3
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#
1
2
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 == 91 <= 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#
Create a DP array where dp[t] is the largest string that can be formed with total cost t.
Initialize dp[0] as empty string.
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.
If dp[target] is empty, return “0”.
Otherwise, return dp[target].
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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() }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.