We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Form Largest Integer With Digits That Add up to Target

Difficulty: Hard

Problem Description

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

Key Insights

  • The problem requires constructing the largest possible integer while adhering to a specified cost constraint.
  • A greedy approach can be applied, specifically choosing digits that provide the largest numerical value for the least cost.
  • The digits must be arranged in a way that maximizes their value, prioritizing higher digits where possible.

Space and Time Complexity

Time Complexity: O(target * 9) - where 9 is the number of digits, as we explore the cost for each digit up to the target. Space Complexity: O(target) - for storing the dynamic programming results.

Solution

The approach involves using dynamic programming to determine the maximum number that can be formed for each cost up to the target. We maintain an array to store the best possible number string for each cost. The algorithm iterates over all possible costs for each digit, updating the best number string when a better option is found.

Code Solutions

def largestNumber(cost, target):
    dp = [""] * (target + 1)
    dp[0] = ""  # Base case: cost 0 corresponds to an empty string
    
    for i in range(9):  # Iterate over digits 1 to 9
        for j in range(cost[i], target + 1):  # Iterate over possible costs
            if dp[j - cost[i]] != "":  # Check if we can form a number with the remaining cost
                new_number = dp[j - cost[i]] + str(i + 1)
                if len(new_number) > len(dp[j]) or (len(new_number) == len(dp[j]) and new_number > dp[j]):
                    dp[j] = new_number  # Update if we found a larger number
    
    return dp[target] if dp[target] else "0"
← Back to All Questions