3723. Maximize Sum of Squares of Digits

MediumGreedyMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two positive integers num and sum.

A positive integer n is called good if it meets both of these conditions:

n has exactly num digits.
The digits of n add up to exactly sum.

The score of a good integer n is defined as the sum of the squares of its digits. For example, if n = 921, its score is 9^2 + 2^2 + 1^2 = 86.

Your task is to find the good integer that achieves the maximum score, and return it as a string. Two tie-breaking and edge-case rules apply:

If several good integers share the same maximum score, return the largest integer among them.
If no good integer exists at all (for example, when sum is too large to be formed with only num digits), return an empty string "".

In short, you need to construct a num-digit number whose digit sum is sum, while making the sum of squared digits as large as possible — and among all such numbers, pick the numerically greatest one.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Squaring disproportionately rewards large digits, so greedily packing as many 9s as possible maximizes the sum of squared digits.

Open in Flowchart

Intuition

The key observation is that squaring rewards big digits disproportionately. If we have a fixed amount of "digit sum" to distribute among the digits, it is always better to pile it into as few, as large digits as possible rather than spreading it out.

Why? Compare splitting a value a + b across two digits versus keeping it in one digit:

(a + b)^2 = a^2 + b^2 + 2ab > a^2 + b^2 (when a, b > 0)

For example, a single 9 contributes 81 to the score, while splitting it into 8 and 1 only gives 64 + 1 = 65, and splitting into 5 and 4 gives just 25 + 16 = 41. Concentration always wins.

This immediately suggests a greedy strategy: use as many 9s as possible. Take k = sum // 9 nines, and if there is a leftover s = sum % 9, put it in one extra digit. All remaining positions are filled with 0, which costs nothing — 0 adds neither to the digit sum nor to the score.

This construction also conveniently handles the tie-breaking rule. To make the resulting number numerically largest, we simply place the digits in descending order: the 9s first, then the leftover digit s, then the trailing 0s. Since the first digit is at least 9 (or s > 0 when sum < 9), the number never starts with a leading zero.

Finally, feasibility is easy to check up front: with num digits, the largest achievable digit sum is num * 9. If sum > num * 9, no good integer can exist, and we return "". (Note that sum can never be "too small" to matter here, since sum is positive and zeros fill the rest.)

Pattern Learn more about Greedy and Math patterns.

Solution Approach

The solution is a direct greedy construction — no extra data structures are needed beyond simple string building. Let's walk through it step by step.

Step 1: Feasibility check.

Each digit can contribute at most 9 to the digit sum, so with num digits the maximum reachable sum is num * 9. If num * 9 < sum, no good integer exists:

if num * 9 < sum:
    return ""

Step 2: Decompose sum into nines plus a remainder.

We compute how many full 9s fit into sum, and what is left over, in one call:

k, s = divmod(sum, 9)

Here k = sum // 9 is the count of 9 digits, and s = sum % 9 is the leftover value with 0 <= s <= 8.

Step 3: Build the answer in descending digit order.

Start with k nines — placing the largest digits first guarantees the result is the numerically greatest among all optimal answers:

ans = "9" * k

If the remainder s is nonzero, append it as a single digit right after the nines (digits[s] is simply the character form of s, equivalent to str(s)):

if s:
    ans += digits[s]

Finally, pad the string with 0s so the total length is exactly num. Zeros change neither the digit sum nor the score:

ans += "0" * (num - len(ans))

Why this is correct and maximal:

The digit sum is 9k + s = sum by construction, and the length is exactly num, so the result is a good integer.
The score 81k + s^2 is the largest possible, because any redistribution of the sum into more, smaller digits strictly decreases the sum of squares (as shown by (a + b)^2 > a^2 + b^2).
Ordering the digits as 9... s 0...0 (non-increasing) yields the largest numeric value among all permutations of these digits.

Complexity Analysis:

Time complexity: O(num) — building the output string of length num dominates; the arithmetic itself is O(1).
Space complexity: O(num) for the answer string (or O(1) if the output is not counted).

Example Walkthrough

Let's trace the greedy construction with num = 5 and sum = 12.

Step 1: Feasibility check.

The maximum digit sum achievable with 5 digits is 5 * 9 = 45. Since 45 >= 12, a good integer exists, so we proceed instead of returning "".

Step 2: Decompose sum into nines plus a remainder.

k, s = divmod(12, 9)   # k = 1, s = 3

So the optimal digit multiset is one 9, a leftover digit 3, and zeros for the rest.

Step 3: Build the answer in descending digit order.

Action	String so far
Append `k = 1` nine	`"9"`
`s = 3` is nonzero → append it	`"93"`
Pad with `num - 2 = 3` zeros	`"93000"`

The result is "93000":

Length is exactly 5 ✓
Digit sum is 9 + 3 + 0 + 0 + 0 = 12 ✓
Score is 9² + 3² = 81 + 9 = 90

Why no other good integer beats it:

Compare a few alternative ways to distribute the same digit sum of 12 across 5 digits:

Candidate	Digits	Score
`93000` (greedy)	9, 3, 0, 0, 0	`81 + 9 =` `90`
`84000`	8, 4, 0, 0, 0	`64 + 16 = 80`
`66000`	6, 6, 0, 0, 0	`36 + 36 = 72`
`33330`	3, 3, 3, 3, 0	`9 × 4 = 36`

Concentrating the sum into the fewest, largest digits clearly wins — exactly the (a + b)² > a² + b² effect.

Tie-breaking check: other arrangements of the same optimal digits, such as 90300 or 39000, share the score 90, but sorting digits in descending order makes 93000 the numerically largest, satisfying the tie-breaking rule.

Edge case for contrast: with num = 2 and sum = 19, the cap is 2 * 9 = 18 < 19, so Step 1 immediately returns "".

Solution Implementation

1class Solution:
2    def maxSumOfSquares(self, num: int, sum: int) -> str:
3        # If even using the maximum digit 9 in every position
4        # cannot reach the target sum, no valid number exists.
5        if num * 9 < sum:
6            return ""
7
8        # Greedy strategy: to maximize the sum of squares of digits,
9        # concentrate the value into as many 9s as possible.
10        # quotient  -> how many full 9s we can place
11        # remainder -> the leftover value (0..8) for one extra digit
12        quotient, remainder = divmod(sum, 9)
13
14        # Start the result with all the 9s.
15        result = "9" * quotient
16
17        # If there is a leftover value, append it as a single digit.
18        if remainder:
19            result += str(remainder)
20
21        # Pad the remaining positions with 0s to reach exactly `num` digits.
22        result += "0" * (num - len(result))
23
24        return result
25

1class Solution {
2    /**
3     * Constructs the largest possible number string with exactly {@code num} digits
4     * whose digit sum equals {@code sum}, using a greedy strategy:
5     * place as many 9s as possible at the front, then the remainder, then pad with 0s.
6     *
7     * @param num the total number of digits the result must contain
8     * @param sum the required sum of all digits
9     * @return the largest valid number string, or an empty string if impossible
10     */
11    public String maxSumOfSquares(int num, int sum) {
12        // If even filling every position with 9 cannot reach the target sum,
13        // no valid number exists.
14        if (num * 9 < sum) {
15            return "";
16        }
17
18        // Greedily determine how many leading 9s can be placed.
19        int nineCount = sum / 9;
20        // The remaining digit value after placing all the 9s.
21        int remainder = sum % 9;
22
23        // Start building the answer with the leading 9s.
24        StringBuilder result = new StringBuilder("9".repeat(nineCount));
25
26        // Append the leftover digit (if any) right after the 9s
27        // to keep the number as large as possible.
28        if (remainder > 0) {
29            result.append(remainder);
30        }
31
32        // Pad the remaining positions with 0s to reach exactly num digits.
33        result.append("0".repeat(num - result.length()));
34
35        return result.toString();
36    }
37}
38```
39
40**Explanation of the approach:**
41
421. **Feasibility check** — Each digit can contribute at most 9, so if `num * 9 < sum`, the target sum is unreachable and an empty string is returned.
432. **Greedy placement of 9s** — To maximize the number's value, the largest digits must appear in the highest (leftmost) positions. `sum / 9` gives the count of full 9s.
443. **Remainder digit** — `sum % 9` is appended next, ensuring the digit sum is exactly met while keeping larger digits earlier.
454. **Zero padding** — The rest of the positions are filled with 0s so the result has exactly `num` digits.
46
47**Alternative perspective:** Instead of arithmetic division, you could build the string digit by digit, subtracting `min(9, sum)` from `sum` at each position. This loop-based version is more intuitive but slightly less concise:
48
49```java
50StringBuilder result = new StringBuilder();
51for (int i = 0; i < num; i++) {
52    int digit = Math.min(9, sum);
53    result.append(digit);
54    sum -= digit;
55}
56

1class Solution {
2public:
3    string maxSumOfSquares(int num, int sum) {
4        // If even filling every digit with 9 cannot reach the target sum,
5        // there is no valid number, so return an empty string.
6        if (num * 9 < sum) {
7            return "";
8        }
9
10        // To maximize the number, place as many 9s as possible at the front.
11        // nineCount: how many full 9s we can use.
12        // remainder: the leftover digit value after using the 9s.
13        int nineCount = sum / 9;
14        int remainder = sum % 9;
15
16        // Start the answer with nineCount consecutive '9' characters.
17        string ans(nineCount, '9');
18
19        // If there is a leftover value, append it as the next digit.
20        if (remainder > 0) {
21            ans += char('0' + remainder);
22        }
23
24        // Pad the rest of the number with '0's to reach exactly num digits.
25        ans += string(num - ans.size(), '0');
26
27        return ans;
28    }
29};
30

1/**
2 * Construct the largest possible number string of length `num`
3 * whose digits add up exactly to `sum`.
4 *
5 * Greedy strategy:
6 * 1. Use as many '9' digits as possible at the front (to maximize the value).
7 * 2. Place the remainder (sum % 9) as the next digit, if it is non-zero.
8 * 3. Pad the rest with '0' digits to reach the required length.
9 *
10 * @param num - The required number of digits in the result.
11 * @param sum - The required total of all digits.
12 * @returns The largest valid number string, or an empty string if impossible.
13 */
14function maxSumOfSquares(num: number, sum: number): string {
15    // If even filling every position with '9' cannot reach `sum`,
16    // no valid result exists.
17    if (num * 9 < sum) {
18        return '';
19    }
20
21    // Number of full '9' digits we can place.
22    const nineCount: number = Math.floor(sum / 9);
23
24    // Remaining digit value after placing all '9's.
25    const remainder: number = sum % 9;
26
27    // Start with the maximal run of '9's.
28    let result: string = '9'.repeat(nineCount);
29
30    // Append the leftover digit if there is any remainder.
31    if (remainder > 0) {
32        result += String.fromCharCode('0'.charCodeAt(0) + remainder);
33    }
34
35    // Pad with '0's to satisfy the required length.
36    if (result.length < num) {
37        result += '0'.repeat(num - result.length);
38    }
39
40    return result;
41}
42

Time and Space Complexity

Time Complexity: O(num). Although computing divmod(sum, 9) takes constant time, constructing the result string requires string operations such as "9" * k and "0" * (num - len(ans)), where k can be up to num / 9 and the padding can be up to num characters. Therefore, building the final string of length num dominates the running time, giving O(num) overall.
Space Complexity: O(num). The answer string ans has a length of exactly num characters (when a valid answer exists), so the space required to store the result grows linearly with num.

Here, num denotes the number of digits in the good integer.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Skipping the feasibility check and producing a silently wrong answer

The most dangerous mistake is omitting (or misplacing) the check num * 9 < sum. What makes this pitfall especially nasty in Python is that the buggy code does not crash — it quietly returns a string of the wrong length.

Consider this faulty version:

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        quotient, remainder = divmod(sum, 9)   # no feasibility check!
        result = "9" * quotient
        if remainder:
            result += str(remainder)
        result += "0" * (num - len(result))
        return result

Trace it with num = 2, sum = 20:

divmod(20, 9) gives quotient = 2, remainder = 2.
result = "99", then "992" after appending the remainder — already 3 digits.
The padding step computes "0" * (2 - 3) = "0" * (-1), which in Python is simply the empty string — no exception, no warning.
The function returns "992", a 3-digit number, when the correct answer is "".

Because Python silently evaluates "0" * negative_number as "", the bug never raises an error and easily slips past casual testing — it only fails on inputs where sum > num * 9.

A related variant of the same trap: placing the check after building the string, or checking quotient > num instead. The latter still misses cases like num = 1, sum = 10 (quotient = 1, remainder = 1 → returns "91", a 2-digit number for a 1-digit requirement).

Solution: validate feasibility first, using the tight bound num * 9 < sum, and return "" immediately before any construction begins:

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        # Guard clause MUST come first: the maximum achievable
        # digit sum with `num` digits is 9 * num.
        if num * 9 < sum:
            return ""

        quotient, remainder = divmod(sum, 9)
        result = "9" * quotient
        if remainder:
            result += str(remainder)
        result += "0" * (num - len(result))
        return result

Once the guard is in place, the rest of the construction is provably safe: quotient <= num, and quotient + 1 <= num whenever remainder > 0, so the padding count num - len(result) is never negative.

Defensive alternative: if you want the code to fail loudly rather than silently in case of future edits, add an assertion before returning:

assert len(result) == num, "constructed number has wrong digit count"

Bonus pitfall: shadowing the built-in `sum`

The parameter name sum (dictated by the problem signature) shadows Python's built-in sum() function inside the method. The given solution never calls the built-in, so it works — but if you later refactor to something like sum(int(d) for d in result) for verification, you'll get a confusing TypeError: 'int' object is not callable. If you extend the code, rename the parameter internally (e.g., target = sum on the first line) before doing any list-based summation.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: