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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Form Largest Integer With Digits That Add up to Target

Number: 1545

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array cost of length 9 where cost[i] represents the cost of painting the digit (i+1) and a target cost, find the largest possible integer (as a string) that can be painted such that the total cost equals target. The integer must only contain digits 1 to 9 and if no valid integer can be painted, return "0".

Key Insights

  • To maximize the integer, we should use as many digits as possible because a longer number is numerically larger.
  • Once the maximum number of digits is determined, prioritize placing larger digits in higher-value positions.
  • Use dynamic programming to determine the maximum number of digits that can be painted for every possible cost up to target.
  • The DP state dp[i] represents the maximum count of digits that can be formed with exactly cost i.
  • After computing the maximum count, reconstruct the largest possible number by greedily picking the highest possible digit that maintains the optimal digit count at each step.

Space and Time Complexity

Time Complexity: O(target * 9) – We iterate through each target value and try all 9 digits. Space Complexity: O(target) – We maintain a DP array of size target + 1.

Solution

We solve the problem using dynamic programming. The main idea is:

  1. Initialize a DP array where dp[i] represents the maximum number of digits that can be formed with cost i. Set dp[0] = 0 and all other entries to a sentinel value (e.g., -infinity) to indicate an impossible cost.
  2. For each total cost from 1 to target, for each digit from 1 to 9 (using its corresponding cost), if the cost allows (i.e., current target i is at least the cost for that digit) and dp[i - digitCost] is valid, update dp[i] with the maximum of its current value and dp[i - digitCost] + 1.
  3. If dp[target] remains impossible, return "0".
  4. Otherwise, reconstruct the result by iteratively selecting, from the highest digit (9) down to 1, the digit that if chosen, ensures the remaining cost can still yield the required number of digits (i.e., dp[remainder] equals dp[remainder - digitCost] + 1). Append the chosen digit to the result string and decrement the remainder.
  5. Output the result string as the largest possible integer.

Code Solutions

# Python Implementation
def largestNumber(cost, target):
    # dp[i] will hold the maximum number of digits we can form with cost i.
    dp = [-float('inf')] * (target + 1)
    dp[0] = 0
    
    # Build the DP table
    for t in range(1, target + 1):
        for i in range(9):  # i from 0 to 8 represents digit i+1.
            if t >= cost[i]:
                dp[t] = max(dp[t], dp[t - cost[i]] + 1)
    
    # If it's impossible to form any number, return "0"
    if dp[target] < 0:
        return "0"
    
    # Reconstruct the largest number
    t = target
    result = []
    for d in range(9, 0, -1):  # Try digits 9 to 1 (largest digit first)
        while t >= cost[d - 1] and dp[t] == dp[t - cost[d - 1]] + 1:
            result.append(str(d))  # Append the digit as a string
            t -= cost[d - 1]
    return "".join(result)

# Example usage:
print(largestNumber([4,3,2,5,6,7,2,5,5], 9))  # Output: "7772"
← Back to All Questions