Valizada's blog

Form largest integer with digits that add up to target leetcode dynamic programming

Dynamic programming solutions are just a pleasure to read! Here is another one from Biweekly leetcode contest 26 to a problem that can be solved with bottom-up DP.

Problem 1449. Form Largest Integer With Digits That Add up to Target:

Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

  1. The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
  2. The total cost used must be equal to target.
  3. Integer does not have digits 0.

Since the answer may be too large, return it as string. If there is no way to paint any integer given the condition, return "0".

Lets now look at the below example input and understand the question:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9

Cost array can be seen as price that needs to be paid to use/paint a digit on a given index:

Digit Cost
1 4
2 3
3 2
4 5
5 6
6 7
7 2
8 5
9 5

Explanation: The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 3 times digit 7 plus once digit 2 = 3 * 2 + 1*3 = 9. You could also paint "997", but "7772" is the largest number.

So, how do we come up with this answer? - one way is to brute force by checking combinations of each digit and making sure the cost adds up to the target, however that is exponential and wont help for big inputs.

Then, what do we do? - We are asked to come up with the maximum possible integer/number. More digits in a number, bigger it is. Lets follow next two steps:

1. Find maximum number of digits that can be used
2. Use biggest digits to construct the number

This is where DP comes to rescue, we will calculate max count of allowed digits starting from 1 up to target. We will use above example case as we go to demonstrate the result.

Let's declare a DP array (maxDigitsCount) to hold answers. We initialise all values with negative infinity, smallest integer in Java. We only set result for number 0 as nothing can be built for target 0.

var maxDigitsCount = new int[target + 1];
Arrays.fill(maxDigitsCount, Integer.MIN_VALUE);
          
maxDigitsCount[0] = 0;

*Arrays.fill(array, value) - a very hand java util to update array entries by hiding for each underneath

Here is how our maxDigitsCount array looks for now: | Index | Max digits count
| :-------------: |:-------------: | 0 | 0 | 1 | -INF | 2 | -INF | 3 | -INF | 4 | -INF | 5 | -INF | 6 | -INF | 7 | -INF | 8 | -INF | 9 | -INF

Now, we iterate starting from 1 till 9 (Target) and on every iteration scan cost array to find any digit that can be afforded.

Starting with 1, in cost array, there is no single affordable digit, hence its value not updated and remains negative infinity.

Index Max digits count
0 0
1 -INF

Next up is 2, two digits satisfy our condition, 3 and 7. Notice in the computation of cost, 2 and 6 used instead as cost array is zero-indexed.

  • maxDigitsCount[2] = Math.max(maxDigitsCount[2], 1 + maxDigitsCount[2 - cost[2]] = Math.max(-INF, 1 + maxDigitsCount[0]) = 1;
  • maxDigitsCount[2] = Math.max(maxDigitsCount[2], 1 + maxDigitsCount[2 - cost[6]] = Math.max(1, 1 + maxDigitsCount[0]) = 1;

In the end, our updated maxDigitsCount array looks like below. This means we can have a maximum of 4 digits for the target of 9. Next is to construct digits that can give us this value.

Index Max digits count
0 0
1 -INF
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 4
// More digits in a number bigger it can be
// Count maximum possible digits till given target in bottom up approach
for(int i = 1; i <= target; i++) {
// iterate over cost array to find affordable amount per current target
  for(int c = 0; c < cost.length; c++) {
    if(i >= cost[c]) {
      maxDigitsCount[i] = Math.max(maxDigitsCount[i], 
                                  1 + maxDigitsCount[i - cost[c]]);
    }
  }
}
  • Math.max(value1, value2) - Handy Math library, saves us from creating temp values. Also check out, Math.min, Math.pow

Before, carrying on with reconstruction, we need to check the edge case where it is not even possible to have the exact target. This is when maxDigitsCount has not been updated at all, hence value remains -INF, meaning less than 0

// no digits can build up exact required target
if(maxDigitsCount[target] < 0) {
  return "0";
}

This is the last challenging bit, we know max number of digits we can use, 4. The biggest we could come up with would be 9999. However, we need to check if the cost of the digit allows us to use it.

Hence the first check is:

    1. Target must be more than cost of the current digit:

      target - cost[i] >= 0

Next, we need to be sure that once we use up a digit, the remaining value is enough to build the rest of the digits. Every time we use/paint a digit, it is one less digit that we are allowed to use.

  • Once we paint current digit, next target must have one less digit

    maxDigitsCount[target] - maxDigitsCount[target - cost[i]] == 1

Let's break it down step by step for our example, the target is 9 and max allowed digits is 4:

  1. Both digit 9 and 8 cost 5 units. It is more than our Target hence we need to pass
  2. Digit 7 costs 2, we can afford it. Also, maxDigitsCount[9] - maxDigitsCount[9 - 2] = 4 - 3 = 1
  3. This repeats trice
  4. The new target is 3 at this point and next digit satisfying both conditions is 2

The final result is: "7772"

Please see below for the whole code:

class Solution {
    public String largestNumber(int[] cost, int target) {
        var maxDigitsCount = new int[target + 1];
        Arrays.fill(maxDigitsCount, Integer.MIN_VALUE);
        
        maxDigitsCount[0] = 0;
        
        // More digits in a number bigger it can be
        // Hence, count maximum possible digits till given target in bottom up approach
        for(int i = 1; i <= target; i++) {
            // iterate over cost array to find affordable amount per current target
            for(int c = 0; c < cost.length; c++) {
                if(i >= cost[c]) {
                    maxDigitsCount[i] = Math.max(maxDigitsCount[i], 
                                                 1 + maxDigitsCount[i - cost[c]]);
                }
            }
        }
        
        // no digits can build up exact required target
        if(maxDigitsCount[target] < 0) {
            return "0";
        }
        
        // iterate starting from highest digit to build up biggest number
        var s = new StringBuilder();
        for(int i = cost.length - 1; i >= 0; i--) {
            // To afford painting current digit, following two constraints must be met
            // 1. Target must be more that cost of the current digit
            // 2. if we paint current digit, next target must have one less digit
            while(target - cost[i] >= 0
                 && maxDigitsCount[target] - maxDigitsCount[target - cost[i]] == 1) {
                target -= cost[i];
                // i + 1 - > gives actual digit to paint
                s.append(i + 1);
            }
        }
        
        return s.toString();
    }
}