Hard

Quiz

#1449 Form Largest Integer With Digits That Add up to Target

APPROACH

You are given a cost array cost where cost[i] is the price to use digit (i+1) (0-indexed), and an integer target representing your exact budget. Construct the numerically largest integer such that the total cost of all its digits equals exactly target. Return the result as a string. If no valid integer can be formed, 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.

1 of 4

1:00

What is the optimal approach for this problem?