Jobs

Interviews

Discussions

Form Largest Integer With Digits That Add up to Target

Hard

Asked by:

23 views

Topics:

Dynamic Programming

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

Try coding it in LeetCode

Form Largest Integer With Digits That Add up to Target

Hard

Asked by:

23 views

Topics:

Dynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the target value? Can it be zero or negative?
Can the cost array contain zero values? If so, what digit should I associate with a zero cost?
If it's impossible to form any integer that sums to the target, what should I return?
If multiple largest integers can be formed, should I return any one of them, or is there a specific tie-breaking rule?
What is the maximum length of the cost array, and the maximum value in the cost array?

Brute Force Solution

Approach

The brute force approach tries all possible combinations of digits to find the largest possible number that meets the target sum. We essentially explore every possible sequence of digits and keep the best one that adds up to the target. It's like trying out every single password combination until you find the right one.

Here's how the algorithm would work step-by-step:

Start by trying all possible single-digit numbers.
See if any of those numbers exactly match the target sum.
If you don't find a single digit number that matches, then try all combinations of two-digit numbers (like 11, 12, 13, etc.) formed by your digits.
For each combination, check if the sum of those digits matches the target. If it does, note down the number.
Keep increasing the number of digits in your combinations (three-digit numbers, four-digit numbers, and so on).
Each time, check if the sum of the digits equals the target. If the sum matches, record the number if it's bigger than any number you've found before.
Continue this process until you've exhausted all possible combinations or you find the largest possible number that matches the sum.
The largest number you recorded during the process is the answer.

Code Implementation

def form_largest_integer_brute_force(cost, target):
    largest_number = ""

    def find_largest(current_number, remaining_target):
        nonlocal largest_number

        # If the target is zero, we've found a valid number.
        if remaining_target == 0:
            if current_number == "" and largest_number == "":
                return
            elif current_number == "":
                return
            elif largest_number == "" or int(current_number) > int(largest_number):
                largest_number = current_number
            return

        # If the target is negative, this combination is invalid.
        if remaining_target < 0:
            return

        for digit in range(9, 0, -1):
            # Attempt to use each digit to reach the target.
            digit_cost = cost[digit - 1]

            find_largest(current_number + str(digit), remaining_target - digit_cost)

    find_largest("", target)
    # If no combination was found, return '0'.
    return largest_number if largest_number else "0"

Big(O) Analysis

Time Complexity

O(9^target) – The brute force approach explores all possible combinations of digits (1-9) to reach the target sum. In the worst-case scenario, it has to try every possible combination of digits until the sum of the digits equals the target value. Imagine the target value is small, like 5. It has to try sequences like '11111', '1112', etc. The maximum number of digits required is `target` because the smallest digit to reach the target is by only using 1. For each digit, we have 9 options (1-9). This leads to potentially 9 choices for each of the 'target' possible digit places, so the total operations are approximately 9 raised to the power of target (9^target).

Space Complexity

O(1) – The brute force approach described primarily involves iterating through digit combinations and tracking the largest number found so far. No significant auxiliary data structures are used to store intermediate combinations; the algorithm only needs to store the current digit combination being tested and the largest number found so far. Therefore, the space required remains constant, irrespective of the target value or the possible digits. Thus, the space complexity is O(1).

Optimal Solution

Approach

The trick is to find the best combination of digits from right to left, treating it like making change for a given amount, but aiming for the biggest result instead of the smallest number of coins. We want to use the largest digit possible for each 'denomination' to construct the integer in a greedy manner. Dynamic programming allows us to determine which digit combination yields the largest integer possible for each target value up to the total target.

Here's how the algorithm would work step-by-step:

First, build a table that tells you the best possible digit (largest) to use to reach a given target value, starting from 0 up to the desired target. This table will be built starting from smaller target values to larger target values.
For each target value in our table, consider each possible digit (9 down to 1) to see if using that digit would improve our result.
If using a particular digit results in a possible smaller target value in our table with a valid solution, and using that digit leads to a better solution than our current solution for the overall target, then update our table to remember that we made this decision.
Work through the table from smaller values to larger values until the whole table is filled.
Once the table is complete, start from the target and retrace the steps you made to arrive at the largest possible integer using the digits you selected.
By systematically choosing the largest digits possible while working towards the total target, you avoid testing all possible combinations and arrive at the solution efficiently.

Code Implementation

def form_largest_integer(cost, target):
    digit_count = len(cost)
    dp = ["" for _ in range(target + 1)]

    # Initialize base case: target 0 can be reached with an empty string.
    dp[0] = ""

    for current_target in range(1, target + 1):
        for digit in range(digit_count - 1, -1, -1):
            digit_value = digit + 1
            cost_of_digit = cost[digit]

            if current_target >= cost_of_digit and dp[current_target - cost_of_digit] != None:
                # Check if adding the digit makes a better solution.
                possible_solution = dp[current_target - cost_of_digit] + str(digit_value)

                if dp[current_target] == "" or len(possible_solution) > len(dp[current_target]) or \
                   (len(possible_solution) == len(dp[current_target]) and possible_solution > dp[current_target]):

                    #Update DP with new largest integer.
                    dp[current_target] = possible_solution

    if dp[target] == "":
        return "0"

    return dp[target]

Big(O) Analysis

Time Complexity

O(target) – The dominant operation is building the dynamic programming table. The outer loop iterates from 1 up to the target value. The inner loop iterates from 9 down to 1 (a constant number of iterations). Within the inner loop, we perform constant-time operations (checking conditions and potentially updating the table). Therefore, the time complexity is directly proportional to the target value. Since the number of iterations is dependent on the 'target' value, the time complexity is O(target).

Space Complexity

O(target) – The algorithm uses a table (likely an array or list) to store the best possible digit to use for each target value, from 0 up to the desired target. The size of this table directly depends on the target value itself, requiring space proportional to the target. Retracing the steps does not involve creating new data structures that scale with the input; it simply reads from the already allocated table. Therefore, the auxiliary space complexity is O(target).

Edge Cases

Case	How to Handle
Target is zero	If target is zero, and cost array contains zero, return '0' repeated as many times as possible, otherwise return an empty string or appropriate error depending on requirements.
No combination of digits adds up to the target	Return an empty string or specific error value like '-1' when no solution is possible, indicating an invalid target or cost array.
Large target value with small digit costs	Be mindful of potential integer overflow or excessive memory usage if the resulting string becomes very long; consider limiting the string length or throwing an exception if a limit is exceeded.
Cost array contains zero but the index is not zero (e.g., cost[5] = 0)	If zero cost is present at a non-zero index, it creates the potential to infinitely append that digit; it must be checked for explicitly and handled by returning the largest possible string using this index.
Cost array contains negative values	If cost array contains negative values, it makes the problem unbounded (infinitely reducing the cost to get closer to target) and the problem becomes meaningless, should handle by throwing an error or returning an appropriate failure response.
Target is small, but the most 'valuable' digits have high costs	Ensure the algorithm correctly chooses the digits that lead to the largest number even if they are not the cheapest or have the smallest indices.
Integer overflow when calculating intermediate values	Carefully choose the data types for intermediate calculations and consider using larger data types to prevent overflow, or using an algorithm that avoids intermediate sums which may overflow.
Input cost array is null or empty	Return an empty string or signal an error if the input cost array is invalid, since a valid calculation cannot be performed.

Target is zero

How to Handle:

If target is zero, and cost array contains zero, return '0' repeated as many times as possible, otherwise return an empty string or appropriate error depending on requirements.

No combination of digits adds up to the target

How to Handle:

Return an empty string or specific error value like '-1' when no solution is possible, indicating an invalid target or cost array.

Large target value with small digit costs

How to Handle:

Be mindful of potential integer overflow or excessive memory usage if the resulting string becomes very long; consider limiting the string length or throwing an exception if a limit is exceeded.

Cost array contains zero but the index is not zero (e.g., cost[5] = 0)

How to Handle:

If zero cost is present at a non-zero index, it creates the potential to infinitely append that digit; it must be checked for explicitly and handled by returning the largest possible string using this index.

Cost array contains negative values

How to Handle:

If cost array contains negative values, it makes the problem unbounded (infinitely reducing the cost to get closer to target) and the problem becomes meaningless, should handle by throwing an error or returning an appropriate failure response.

Target is small, but the most 'valuable' digits have high costs

How to Handle:

Ensure the algorithm correctly chooses the digits that lead to the largest number even if they are not the cheapest or have the smallest indices.

Integer overflow when calculating intermediate values

How to Handle:

Carefully choose the data types for intermediate calculations and consider using larger data types to prevent overflow, or using an algorithm that avoids intermediate sums which may overflow.

Input cost array is null or empty

How to Handle:

Return an empty string or signal an error if the input cost array is invalid, since a valid calculation cannot be performed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the target value? Can it be zero or negative?
Can the cost array contain zero values? If so, what digit should I associate with a zero cost?
If it's impossible to form any integer that sums to the target, what should I return?
If multiple largest integers can be formed, should I return any one of them, or is there a specific tie-breaking rule?
What is the maximum length of the cost array, and the maximum value in the cost array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by trying all possible single-digit numbers.
See if any of those numbers exactly match the target sum.
If you don't find a single digit number that matches, then try all combinations of two-digit numbers (like 11, 12, 13, etc.) formed by your digits.
For each combination, check if the sum of those digits matches the target. If it does, note down the number.
Keep increasing the number of digits in your combinations (three-digit numbers, four-digit numbers, and so on).
Each time, check if the sum of the digits equals the target. If the sum matches, record the number if it's bigger than any number you've found before.
Continue this process until you've exhausted all possible combinations or you find the largest possible number that matches the sum.
The largest number you recorded during the process is the answer.

Code Implementation

def form_largest_integer_brute_force(cost, target):
    largest_number = ""

    def find_largest(current_number, remaining_target):
        nonlocal largest_number

        # If the target is zero, we've found a valid number.
        if remaining_target == 0:
            if current_number == "" and largest_number == "":
                return
            elif current_number == "":
                return
            elif largest_number == "" or int(current_number) > int(largest_number):
                largest_number = current_number
            return

        # If the target is negative, this combination is invalid.
        if remaining_target < 0:
            return

        for digit in range(9, 0, -1):
            # Attempt to use each digit to reach the target.
            digit_cost = cost[digit - 1]

            find_largest(current_number + str(digit), remaining_target - digit_cost)

    find_largest("", target)
    # If no combination was found, return '0'.
    return largest_number if largest_number else "0"

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, build a table that tells you the best possible digit (largest) to use to reach a given target value, starting from 0 up to the desired target. This table will be built starting from smaller target values to larger target values.
For each target value in our table, consider each possible digit (9 down to 1) to see if using that digit would improve our result.
If using a particular digit results in a possible smaller target value in our table with a valid solution, and using that digit leads to a better solution than our current solution for the overall target, then update our table to remember that we made this decision.
Work through the table from smaller values to larger values until the whole table is filled.
Once the table is complete, start from the target and retrace the steps you made to arrive at the largest possible integer using the digits you selected.
By systematically choosing the largest digits possible while working towards the total target, you avoid testing all possible combinations and arrive at the solution efficiently.

Code Implementation

def form_largest_integer(cost, target):
    digit_count = len(cost)
    dp = ["" for _ in range(target + 1)]

    # Initialize base case: target 0 can be reached with an empty string.
    dp[0] = ""

    for current_target in range(1, target + 1):
        for digit in range(digit_count - 1, -1, -1):
            digit_value = digit + 1
            cost_of_digit = cost[digit]

            if current_target >= cost_of_digit and dp[current_target - cost_of_digit] != None:
                # Check if adding the digit makes a better solution.
                possible_solution = dp[current_target - cost_of_digit] + str(digit_value)

                if dp[current_target] == "" or len(possible_solution) > len(dp[current_target]) or \
                   (len(possible_solution) == len(dp[current_target]) and possible_solution > dp[current_target]):

                    #Update DP with new largest integer.
                    dp[current_target] = possible_solution

    if dp[target] == "":
        return "0"

    return dp[target]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Target is zero	If target is zero, and cost array contains zero, return '0' repeated as many times as possible, otherwise return an empty string or appropriate error depending on requirements.
No combination of digits adds up to the target	Return an empty string or specific error value like '-1' when no solution is possible, indicating an invalid target or cost array.
Large target value with small digit costs	Be mindful of potential integer overflow or excessive memory usage if the resulting string becomes very long; consider limiting the string length or throwing an exception if a limit is exceeded.
Cost array contains zero but the index is not zero (e.g., cost[5] = 0)	If zero cost is present at a non-zero index, it creates the potential to infinitely append that digit; it must be checked for explicitly and handled by returning the largest possible string using this index.
Cost array contains negative values	If cost array contains negative values, it makes the problem unbounded (infinitely reducing the cost to get closer to target) and the problem becomes meaningless, should handle by throwing an error or returning an appropriate failure response.
Target is small, but the most 'valuable' digits have high costs	Ensure the algorithm correctly chooses the digits that lead to the largest number even if they are not the cheapest or have the smallest indices.
Integer overflow when calculating intermediate values	Carefully choose the data types for intermediate calculations and consider using larger data types to prevent overflow, or using an algorithm that avoids intermediate sums which may overflow.
Input cost array is null or empty	Return an empty string or signal an error if the input cost array is invalid, since a valid calculation cannot be performed.

Target is zero

How to Handle:

If target is zero, and cost array contains zero, return '0' repeated as many times as possible, otherwise return an empty string or appropriate error depending on requirements.

No combination of digits adds up to the target

How to Handle:

Return an empty string or specific error value like '-1' when no solution is possible, indicating an invalid target or cost array.

Large target value with small digit costs

How to Handle:

Be mindful of potential integer overflow or excessive memory usage if the resulting string becomes very long; consider limiting the string length or throwing an exception if a limit is exceeded.

Cost array contains zero but the index is not zero (e.g., cost[5] = 0)

How to Handle:

Cost array contains negative values

How to Handle:

Target is small, but the most 'valuable' digits have high costs

How to Handle:

Ensure the algorithm correctly chooses the digits that lead to the largest number even if they are not the cheapest or have the smallest indices.

Integer overflow when calculating intermediate values

How to Handle:

Carefully choose the data types for intermediate calculations and consider using larger data types to prevent overflow, or using an algorithm that avoids intermediate sums which may overflow.

Input cost array is null or empty

How to Handle:

Return an empty string or signal an error if the input cost array is invalid, since a valid calculation cannot be performed.