Scale Engineer

Form Largest Integer With Digits That Add up to Target

Hard
#1339Time: O(target^2). There are O(target) subproblems to solve. For each subproblem `solve(t)`, we iterate through 9 digits. Inside the loop, string concatenation and comparison take time proportional to the string length, which can be up to O(t). This gives a total complexity of Σ(9 * t) for t from 1 to target, which is O(target^2).Space: O(target^2). The recursion depth is O(target), and the memoization table `memo` stores O(target) entries. In the worst case, each entry can be a string of length O(target), leading to a total space complexity of O(target^2).
Patterns
Dynamic Programming
Data structures
Array

Prompt

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

 

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach solves the problem using recursion with memoization, which is a top-down dynamic programming technique. We define a function that finds the largest number for a given cost t. To prevent re-calculating results for the same cost, we store them in a memoization table. The function explores adding each possible digit and recursively solves for the remaining cost, always prioritizing choices that lead to a lexicographically larger final number.

Algorithm

  • Define a recursive function solve(t) that returns the largest number string for a given remaining target cost t.
  • Use a memoization table (e.g., an array memo) to store the results of solve(t) to avoid redundant computations.
  • The base case for the recursion is t == 0, which returns an empty string "" indicating a successful path.
  • If t < 0, it's an invalid path, so return a special marker like null.
  • In the recursive step for solve(t), iterate through digits d from 9 down to 1.
  • For each digit d, make a recursive call solve(t - cost[d-1]).
  • If the subproblem returns a valid string, form a candidate string by prepending d.
  • Keep track of the best candidate found for t (one that is longer or lexicographically larger).
  • Store the best result in memo[t] before returning.
  • The initial call is solve(target). If it returns null, no solution exists; otherwise, it's the answer.

Walkthrough

The core of this method is a recursive function, let's call it solve(t), which aims to find the largest number that can be formed with a total cost of t.

To make the resulting number as large as possible, we must follow two principles:

  1. The number should have as many digits as possible.
  2. For two numbers with the same number of digits, the one that is lexicographically larger is preferred (e.g., "95" > "86").

Our recursive function solve(t) will try to append each digit from 9 down to 1. By trying larger digits first, we ensure that if we find multiple numbers of the same maximum length, we will construct the lexicographically largest one.

The state of our recursion is the remaining cost t. The function will return the best string for that cost.

  • Base Cases:

    • If t == 0, we have met the target cost exactly. We return an empty string "" to signify a valid end to the construction.
    • If t < 0, we have overshot the target, so this path is invalid. We return null.

  • Memoization:

    • We use an array memo where memo[t] stores the computed result for solve(t). If memo[t] is already computed, we return it immediately.

  • Recursive Step:

    • We initialize a variable best = null to keep track of the best string for the current cost t.
    • We loop through digits d from 9 down to 1.
    • For each digit, we call solve(t - cost[d-1]).
    • If the recursive call returns a non-null result subResult, we form a new candidate string d + subResult.
    • We compare candidate with best. If candidate is larger (longer, or lexicographically greater for the same length), we update best = candidate.

After checking all digits, we store best in memo[t] and return it. The final answer is solve(target), or "0" if the result is null.

class Solution {    String[] memo;    int[] cost;     public String largestNumber(int[] cost, int target) {        this.cost = cost;        memo = new String[target + 1];        String result = solve(target);        return result == null ? "0" : result;    }     private String solve(int t) {        if (t == 0) {            return "";        }        if (t < 0) {            return null;        }        if (memo[t] != null) {            // We use a special marker for computed but impossible states vs uncomputed states            // For simplicity, if memo[t] is not null, it's computed. If it's a specific value like "IMPOSSIBLE", it's impossible.            // Here, null itself serves as the impossible marker.            return memo[t];        }         String best = null;        for (int d = 9; d >= 1; d--) {            int c = cost[d - 1];            String subResult = solve(t - c);             if (subResult != null) {                String candidate = d + subResult;                if (best == null || isLarger(candidate, best)) {                    best = candidate;                }            }        }                memo[t] = best; // Memoize the result (even if it's null)        return best;    }     private boolean isLarger(String s1, String s2) {        if (s1.length() != s2.length()) {            return s1.length() > s2.length();        }        return s1.compareTo(s2) > 0;    }}

Complexity

Time

O(target^2). There are O(target) subproblems to solve. For each subproblem `solve(t)`, we iterate through 9 digits. Inside the loop, string concatenation and comparison take time proportional to the string length, which can be up to O(t). This gives a total complexity of Σ(9 * t) for t from 1 to target, which is O(target^2).

Space

O(target^2). The recursion depth is O(target), and the memoization table `memo` stores O(target) entries. In the worst case, each entry can be a string of length O(target), leading to a total space complexity of O(target^2).

Trade-offs

Pros

  • Conceptually straightforward, as it directly models the recursive nature of the problem.

  • Guaranteed to find the optimal solution due to exhaustive search over possibilities.

Cons

  • The time and space complexity of O(target^2) can be too slow and memory-intensive for large target values.

  • Frequent string concatenations and comparisons inside the recursion are inefficient.

  • Potential for stack overflow errors with deep recursion on very large target values, although constraints make this unlikely.

Solutions

class Solution {public  String largestNumber(int[] cost, int target) {    final int inf = 1 << 30;    int[][] f = new int[10][target + 1];    int[][] g = new int[10][target + 1];    for (var e : f) {      Arrays.fill(e, -inf);    }    f[0][0] = 0;    for (int i = 1; i <= 9; ++i) {      int c = cost[i - 1];      for (int j = 0; j <= target; ++j) {        if (j < c || f[i][j - c] + 1 < f[i - 1][j]) {          f[i][j] = f[i - 1][j];          g[i][j] = j;        } else {          f[i][j] = f[i][j - c] + 1;          g[i][j] = j - c;        }      }    }    if (f[9][target] < 0) {      return "0";    }    StringBuilder sb = new StringBuilder();    for (int i = 9, j = target; i > 0;) {      if (j == g[i][j]) {        --i;      } else {        sb.append(i);        j = g[i][j];      }    }    return sb.toString();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem