Form Largest Integer With Digits That Add up to Target

Form Largest Integer With Digits That Add up to Target

What is this problem about?

The Form Largest Integer With Digits That Add up to Target interview question gives you an array cost of length 9, where cost[i] represents the cost of adding the digit i+1 (from 1 to 9) to your number. You have an exact target cost you must spend. You need to form the largest possible integer. The result is returned as a string since the number can be very large.

Why is this asked in interviews?

Google uses this Hard difficulty Dynamic Programming problem to test a candidate's ability to optimize for multiple criteria. To make an integer "large," you first want to maximize its length (number of digits), and then you want to maximize the values of the digits starting from the most significant bit. It evaluates if you can adapt the classic "Unbounded Knapsack" or "Coin Change" pattern to string generation.

Algorithmic pattern used

This problem uses 1D Dynamic Programming.

1. State: dp[i] stores the maximum length of an integer that can be formed with exactly cost i. Initialize with $-1$ (unreachable) and dp[0] = 0.
2. Transition: For each cost from 1 to target, try adding each digit d (1-9). dp[i] = max(dp[i], dp[i - cost[d-1]] + 1).
3. Reconstruction: After finding the max length for target, work backward to build the string. At cost c, look for the largest digit d (from 9 down to 1) such that dp[c - cost[d-1]] == dp[c] - 1. Append d and update c.

Example explanation

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

• Digit 1 costs 4, Digit 2 costs 3, Digit 3 costs 2...

1. Maximize length: DP determines the max length for cost 9 is 4 (using costs 2, 2, 2, 3).
2. Reconstruct: We have cost 9. We check digits 9 down to 1.
   • Can we use digit 7 (cost 2)? Yes, if dp[9 - 2] == dp[9] - 1 (i.e., dp[7] == 3). Yes, it is. Append "7", new target = 7.
   • For target 7: use digit 7 (cost 2). Append "7", new target = 5.
   • For target 5: use digit 7 (cost 2). Append "7", new target = 3.
   • For target 3: use digit 3 (cost 2)? No. Use digit 2 (cost 3). Append "2", new target = 0. Result: "7772".

Common mistakes candidates make

• Storing Strings in DP: Trying to store the actual string at dp[i]. This causes massive memory overhead and string comparison slows down the DP transitions.
• Greedy approach: Always picking the cheapest digit. The cheapest digit might not exactly sum up to the target, leaving an unused remainder.
• Not prioritizing larger digits: During reconstruction, forgetting to loop from digit 9 down to 1 to ensure the lexicographically largest string.

Interview preparation tip

In "Knapsack" problems where the output is a path or a sequence (like a string of digits), it is almost always better to let the DP compute only the "score" (length) and then do a second pass to trace back the optimal choices.