LeetCode 3723 - Maximize Sum of Squares of Digits

The problem asks us to construct a positive integer n of exactly num digits such that the sum of its digits equals sum.

leetcodemediummathgreedy

LeetCode Problem 3723

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to construct a positive integer n of exactly num digits such that the sum of its digits equals sum. Among all possible integers that satisfy these conditions (called good integers), we must return the integer that maximizes the sum of the squares of its digits, which is called the score. If there are multiple integers achieving the same maximum score, the numerically largest one should be returned. If no such integer exists, we return an empty string.

The input consists of two integers, num and sum. The output is a string representing the desired integer. The constraints are:

  • 1 <= num <= 2 * 10^5
  • 1 <= sum <= 2 * 10^6

These constraints indicate that num can be very large, up to hundreds of thousands of digits, and the sum can also be quite large. Therefore, any approach that enumerates all numbers or all digit permutations is infeasible.

Important edge cases include situations where:

  • sum is too large to be achievable with num digits (e.g., num=1, sum=10).
  • sum is exactly zero (only possible if num=1).
  • sum can be achieved with multiple configurations, requiring us to choose the one that maximizes the score or the numerical value.

Approaches

Brute-Force Approach

A brute-force approach would involve generating all numbers of length num and checking if their digit sum equals sum. For each valid number, we compute the sum of squares of digits, and track the number that produces the maximum score. Finally, if there are multiple numbers with the same score, we choose the largest one numerically.

While this approach guarantees correctness, it is entirely infeasible for large inputs. The number of numbers with num digits is 10^num (minus numbers with leading zeros), which is astronomically large for num up to 2 * 10^5.

Optimal Approach

The key insight is that to maximize the sum of squares of digits, we should use the largest possible digits first. The square function grows quadratically, so putting a 9 instead of smaller digits contributes much more to the score.

Therefore, we can construct the number greedily from left to right, assigning the largest possible digit at each position without exceeding the remaining sum and ensuring that the remaining digits can still reach the remaining sum. After constructing the sequence, reversing it gives the largest numerical value, because the largest digits should appear at the highest place value.

This greedy approach ensures that we maximize the score while satisfying both the digit sum and length constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(10^num) O(num) Generate all numbers and compute scores, infeasible for large num
Optimal O(num) O(num) Greedy construction from largest digit to smallest, linear in number of digits

Algorithm Walkthrough

  1. Check feasibility: If sum > 9 * num, return an empty string because it is impossible to reach the sum with num digits.
  2. Initialize storage: Create a list digits to store each digit of the number.
  3. Construct digits greedily: For each position from 0 to num-1, choose the largest digit possible at that position without exceeding the remaining sum and while leaving enough sum for remaining digits.
  • Let digit = min(9, remaining_sum).
  • Append digit to digits.
  • Subtract digit from remaining_sum.
  1. Check completion: If after filling all digits, remaining_sum > 0, it means it is impossible, so return an empty string.
  2. Build final number: Convert digits to a string. To get the maximum numerical value, reverse the digits list so that the largest digits are at the leftmost positions.
  3. Return the result as a string.

Why it works: By always placing the largest possible digit at each step while respecting the total sum constraint, we ensure the sum of squares is maximized. Reversing for numerical order ensures we choose the lexicographically largest number among equally scoring options.

Python Solution

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        if sum > 9 * num:
            return ""
        
        digits = []
        remaining_sum = sum
        
        for _ in range(num):
            digit = min(9, remaining_sum)
            digits.append(digit)
            remaining_sum -= digit
        
        if remaining_sum > 0:
            return ""
        
        # Reverse to get maximum numerical value
        digits = digits[::-1]
        return ''.join(str(d) for d in digits)

In the implementation, we first check feasibility. We then greedily allocate the largest digits possible, tracking the remaining sum. Finally, reversing the list ensures the largest integer numerically is returned. The list comprehension converts each digit to a string for concatenation.

Go Solution

import "strconv"

func maxSumOfSquares(num int, sum int) string {
    if sum > 9*num {
        return ""
    }
    
    digits := make([]int, num)
    remaining := sum
    
    for i := 0; i < num; i++ {
        digit := remaining
        if digit > 9 {
            digit = 9
        }
        digits[i] = digit
        remaining -= digit
    }
    
    if remaining > 0 {
        return ""
    }
    
    // Reverse to get maximum numerical value
    for i, j := 0, num-1; i < j; i, j = i+1, j-1 {
        digits[i], digits[j] = digits[j], digits[i]
    }
    
    result := ""
    for _, d := range digits {
        result += strconv.Itoa(d)
    }
    
    return result
}

In Go, we handle the digits using a slice and reverse it manually. The conversion of integers to string uses strconv.Itoa. There is no need for handling nil slices as we always initialize the slice with size num.

Worked Examples

Example 1: num = 2, sum = 3

Step Remaining Sum Digit Chosen Digits List
1 3 3 [3]
2 0 0 [3,0]

Reverse → [0,3] → "30"

Score = 3² + 0² = 9

Example 2: num = 2, sum = 17

Step Remaining Sum Digit Chosen Digits List
1 17 9 [9]
2 8 8 [9,8]

Reverse → [8,9] → "98"

Score = 9² + 8² = 145

Example 3: num = 1, sum = 10

sum > 9*num → return ""

Complexity Analysis

Measure Complexity Explanation
Time O(num) We iterate once over num digits to construct the result.
Space O(num) We store the digits in a list/slice of length num.

The linear complexity is optimal, as we need to construct each digit at least once.

Test Cases

s = Solution()

# Provided examples
assert s.maxSumOfSquares(2, 3) == "30"  # Maximum score 9
assert s.maxSumOfSquares(2, 17) == "98" # Maximum score 145
assert s.maxSumOfSquares(1, 10) == ""   # Impossible

# Edge cases
assert s.maxSumOfSquares(1, 1) == "1"   # Minimum num and sum
assert s.maxSumOfSquares(5, 0) == ""    # Sum 0 impossible with 5 digits
assert s.maxSumOfSquares(3, 27) == "999" # Maximum sum possible with 3 digits
assert s.maxSumOfSquares(4, 35) == ""    # Sum too large for 4 digits
assert s.maxSumOfSquares(2, 18) == "99"  # Sum exactly 18
Test Why
num=2,sum=3 Tests normal small case
num=2,sum=17 Tests choosing largest digit for maximum score
num=1,sum=10 Tests impossible sum
num=1,sum=1 Minimum input values
num=5,sum=0 Impossible sum with multiple digits
num=3,sum=27 Maximum sum achievable
num=4,sum=35 Sum too large, impossible
num=2,sum=18 Maximum sum for 2-digit number

Edge Cases

1. Impossible sum: When sum > 9*num, no combination can reach the sum. Our solution immediately returns "".

2. Sum exactly zero: Only valid if num=1. Otherwise, a sum of zero cannot be spread across multiple digits. The solution returns "" for these