Package g1401_1500.s1449_form_largest_integer_with_digits_that_add_up_to_target

Class Solution

java.lang.Object

g1401_1500.s1449_form_largest_integer_with_digits_that_add_up_to_target.Solution

public class Solution
extends Object

1449 - Form Largest Integer With Digits That Add up to Target.<p>Hard</p> <p>Given an array of integers <code>cost</code> and an integer <code>target</code>, return <em>the <strong>maximum</strong> integer you can paint under the following rules</em>:</p> <ul> <li>The cost of painting a digit <code>(i + 1)</code> is given by <code>cost[i]</code> ( <strong>0-indexed</strong> ).</li> <li>The total cost used must be equal to <code>target</code>.</li> <li>The integer does not have <code>0</code> digits.</li> </ul> <p>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 <code>&quot;0&quot;</code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> cost = [4,3,2,5,6,7,2,5,5], target = 9</p> <p><strong>Output:</strong> &ldquo;7772&rdquo;</p> <p><strong>Explanation:</strong> The cost to paint the digit &lsquo;7&rsquo; is 2, and the digit &lsquo;2&rsquo; is 3. Then cost(&ldquo;7772&rdquo;) = 2*3+ 3*1 = 9. You could also paint &ldquo;977&rdquo;, but &ldquo;7772&rdquo; is the largest number.</p> <p><strong>Digit cost</strong></p> <p>1 -> 4</p> <p>2 -> 3</p> <p>3 -> 2</p> <p>4 -> 5</p> <p>5 -> 6</p> <p>6 -> 7</p> <p>7 -> 2</p> <p>8 -> 5</p> <p>9 -> 5</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> cost = [7,6,5,5,5,6,8,7,8], target = 12</p> <p><strong>Output:</strong> &ldquo;85&rdquo;</p> <p><strong>Explanation:</strong> The cost to paint the digit &lsquo;8&rsquo; is 7, and the digit &lsquo;5&rsquo; is 5. Then cost(&ldquo;85&rdquo;) = 7 + 5 = 12.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> cost = [2,4,6,2,4,6,4,4,4], target = 5</p> <p><strong>Output:</strong> &ldquo;0&rdquo;</p> <p><strong>Explanation:</strong> It is impossible to paint any integer with total cost equal to target.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>cost.length == 9</code></li> <li><code>1 <= cost[i], target <= 5000</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
String	largestNumber(int[] cost, int target)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

largestNumber

public String largestNumber(int[] cost,
 int target)