Form Largest Integer With Digits That Add up to Target

Form Largest Integer With Digits That Add up to Target - Problem

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

Input & Output

Example 1 — Basic Case

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

› Output: "77"

💡 Note: We can paint digit 7 twice with cost 2+2=4, but target is 7. We can paint digit 7 (cost 2) and digit 7 (cost 2) plus digit 3 (cost 2) gives us cost 6, but that's not 7. We can paint two 7s with total cost 4, leaving 3 cost remaining. We can use remaining cost 3 to paint digit 2 (cost 3). So we get digits 7,7,2 but we want the largest number, so we arrange as 777 is not possible. Actually, we can paint 7 (cost 2) and 7 (cost 2) and have cost 3 left, which gives us digit 2, so 772 rearranged is 772. But the optimal is 77 using cost 2+2+3=7 where we use digit 2 (cost 3) and digit 7 twice (cost 2 each), giving us digits 2,7,7 rearranged as 772. Wait, let me recalculate: digit 7 costs cost[6]=2, so two 7s cost 4. We need exactly 7. We need 3 more cost. Digit 2 costs cost[1]=3. So we get 7,7,2 with costs 2+2+3=7. The largest arrangement is 772. But the expected output is 77. Let me check: if we only use two 7s, cost is 2+2=4, not 7. We need cost exactly 7. If we use 7,7,3 (where 3 costs 2), total is 2+2+2=6, not 7. If we use 7,7,2 (where 2 costs 3), total is 2+2+3=7 ✓. Result should be 772, not 77.

Example 2 — No Solution

$ Input: cost = [7,6,5,5,5,6,8,7,8], target = 5

› Output: "0"

💡 Note: The minimum cost to paint any digit is 5 (digits 3, 4, 5). With target=5, we can only afford one digit. We can paint digit 3, 4, or 5, each costing exactly 5. The largest possible is digit 5, so result is "5".

Example 3 — Multiple Digits

$ Input: cost = [2,4,6,2,4,6,4,4,4], target = 5

› Output: "0"

💡 Note: Digits 1 and 4 cost 2 each. With target=5, we can paint at most 2 digits (cost 4) with 1 remaining, but no digit costs 1. We could paint one digit: digit 1 costs 2 (3 remaining, no digit costs 3), digit 4 costs 2 (3 remaining, no valid), or no exact match. Actually let me recheck costs: cost[0]=2 (digit 1), cost[3]=2 (digit 4). No digit costs exactly 5, and we can't make 5 with combinations. Wait, let's see: we could paint digit 1 (cost 2) and have 3 remaining, but no digit costs 3. We could paint digit 4 (cost 2) and have 3 remaining, but no digit costs 3. We can't paint two digits with cost 2 each since that would be 4, leaving 1, and no digit costs 1. So no valid solution exists.

Constraints

cost.length == 9
1 ≤ cost[i] ≤ 5000
1 ≤ target ≤ 5000

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

Find max digits possible, then pick largest digits greedily

Output

Largest integer: "772"

Key Takeaway

🎯 Key Insight: Maximize the number of digits first, then greedily pick the largest digits to form the maximum integer

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to maximize the number of digits first, then greedily construct the largest number. Use Dynamic Programming to find the maximum digits achievable, then Greedy Construction to build the lexicographically largest number. Best approach: Two-Phase DP. Time: O(target + digits²), Space: O(target)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(target × 9)	O(target)	Cache recursive results to avoid redundant calculations
Recursive Backtracking	O(9^target)	O(target)	Try all possible combinations of digits recursively
Two-Phase Dynamic Programming	O(target + digits²)	O(target)	First find max digits possible, then construct largest number greedily

Memoized Recursion — Algorithm Steps

Step 1: Create memo table for caching results
Step 2: Check cache before recursive call
Step 3: Store and return computed result

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Compute and cache result for target=7

Subproblems

Cache results for target=5, target=2, etc.

Cache Hit

Reuse cached results when same target appears

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int key;
    char value[1000];
} MemoEntry;

MemoEntry memo[5001];
int memo_size = 0;

char* findMemo(int key) {
    for (int i = 0; i < memo_size; i++) {
        if (memo[i].key == key) {
            return memo[i].value[0] ? memo[i].value : NULL;
        }
    }
    return NULL;
}

void addMemo(int key, char* value) {
    memo[memo_size].key = key;
    if (value) strcpy(memo[memo_size].value, value);
    else memo[memo_size].value[0] = '\0';
    memo_size++;
}

char* dp(int* cost, int remaining, char* buffer) {
    char* cached = findMemo(remaining);
    if (cached) return cached;
    
    if (remaining == 0) {
        buffer[0] = '\0';
        addMemo(remaining, buffer);
        return buffer;
    }
    if (remaining < 0) {
        addMemo(remaining, NULL);
        return NULL;
    }
    
    char* best = NULL;
    char temp[1000];
    for (int digit = 1; digit <= 9; digit++) {
        if (cost[digit-1] <= remaining) {
            char* subResult = dp(cost, remaining - cost[digit-1], temp);
            if (subResult != NULL) {
                sprintf(buffer, "%d%s", digit, subResult);
                if (best == NULL || strlen(buffer) > strlen(best) ||
                    (strlen(buffer) == strlen(best) && strcmp(buffer, best) > 0)) {
                    best = buffer;
                    strcpy(temp, buffer);
                }
            }
        }
    }
    
    addMemo(remaining, best);
    return best;
}

char* solution(int* cost, int target) {
    memo_size = 0;
    static char result[1000];
    char* res = dp(cost, target, result);
    return res ? res : "0";
}

int main() {
    int cost[9];
    char line[100];
    fgets(line, sizeof(line), stdin);
    sscanf(line, "[%d,%d,%d,%d,%d,%d,%d,%d,%d]", &cost[0], &cost[1], &cost[2], &cost[3], &cost[4], &cost[5], &cost[6], &cost[7], &cost[8]);
    
    int target;
    scanf("%d", &target);
    
    printf("%s\n", solution(cost, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(target × 9)

Each target value computed once, trying 9 digits each time

✓ Linear Growth

Space Complexity

O(target)

Memoization table stores result for each target value

✓ Linear Space

28.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler