Watch 6 video solutions for Maximize Sum of Squares of Digits, a medium level problem involving Math, Greedy. This walkthrough by so-um-ya has 962 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two positive integers num and sum.
A positive integer n is good if it satisfies both of the following:
n is exactly num.n is exactly sum.The score of a good integer n is the sum of the squares of digits in n.
Return a string denoting the good integer n that achieves the maximum score. If there are multiple possible integers, return the maximum one. If no such integer exists, return an empty string.
Example 1:
Input: num = 2, sum = 3
Output: "30"
Explanation:
There are 3 good integers: 12, 21, and 30.
12 + 22 = 5.22 + 12 = 5.32 + 02 = 9.The maximum score is 9, which is achieved by the good integer 30. Therefore, the answer is "30".
Example 2:
Input: num = 2, sum = 17
Output: "98"
Explanation:
There are 2 good integers: 89 and 98.
82 + 92 = 145.92 + 82 = 145.The maximum score is 145. The maximum good integer that achieves this score is 98. Therefore, the answer is "98".
Example 3:
Input: num = 1, sum = 10
Output: ""
Explanation:
There are no integers that have exactly 1 digit and whose digits sum to 10. Therefore, the answer is "".
Constraints:
1 <= num <= 2 * 1051 <= sum <= 2 * 106Problem Overview: You need to maximize the total sum(digit^2) formed from a set or representation of digits while preserving the overall numeric constraints (such as total digit sum or allowed transformations). The challenge comes from the fact that squaring favors larger digits, so the distribution of values across digits directly affects the final score.
Approach 1: Greedy Digit Maximization (O(n) time, O(1) space)
The key mathematical insight is that the square function is convex. Moving value from a smaller digit to a larger digit increases the total sum of squares. For example, 1^2 + 5^2 = 26 while 0^2 + 6^2 = 36. Because of this property, the optimal strategy is to concentrate as much value as possible into the largest digits. A greedy approach repeatedly assigns the maximum possible digit value (usually 9) while maintaining the required total digit sum or constraint.
Implementation is straightforward: iterate while there is remaining digit value to distribute. At each step, assign min(9, remaining_sum) to the next digit and subtract it from the remaining total. Each assignment contributes digit * digit to the final score. This greedy allocation ensures the largest digits receive the most value, which maximizes the squared contribution.
This works because any redistribution that moves value from a larger digit to a smaller one reduces the sum of squares. The greedy strategy therefore produces a globally optimal configuration without backtracking or dynamic programming. The algorithm simply processes digits sequentially and performs constant-time arithmetic operations.
Problems like this often appear under greedy and math categories because the optimal solution depends on recognizing the convex behavior of the square function rather than exploring combinations. You iterate through the digits once and maintain a running total.
Recommended for interviews: Interviewers expect the greedy reasoning. A brute-force search over all digit distributions grows exponentially and is unnecessary once you recognize the convex property of squares. Explaining why concentrating value into larger digits increases the objective demonstrates strong mathematical intuition and familiarity with greedy algorithms.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Distribution | Exponential | O(n) | Conceptual baseline when exploring all digit allocations |
| Greedy Digit Maximization | O(n) | O(1) | Optimal approach when maximizing squared digit contribution |