3723. Maximize Sum of Squares of Digits

1. Description

Find a positive integer with exactly num decimal digits whose digits add up to sum.
Its score is the sum of its squared digits. Return the integer with the highest score as a string, choosing the largest integer if several share that score.
Return an empty string when no integer satisfies the digit count and digit sum.

2. Example

Example 1

Input: num = 2, sum = 3
Output: “30”
Explanation: The candidates 12 and 21 each score 5, while 30 scores 3$^2$ + 0$^2$ = 9.

Example 2

Input: num = 2, sum = 17
Output: “98”
Explanation: Both 89 and 98 score 8$^2$ + 9$^2$ = 145. Choose 98 because it is larger.

Example 3

Input: num = 1, sum = 10
Output: ""
Explanation: A single decimal digit cannot have a digit sum of 10.

3. Constraints

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

4. Solutions

Greedy

Time complexity: O(num)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// Concentrate the digit sum into 9s, then a remainder, leaving zeros at the end.
// Placing larger digits first also gives the largest integer among equal scores.
class Solution {
public:
    string maxSumOfSquares(int num, int sum) {
        if (sum > num * 9) {
            return "";
        }

        string number(num, '0');

        for (int i = 0; i < num && sum > 0; ++i) {
            int digit = min(9, sum);
            number[i] += digit;
            sum -= digit;
        }

        return number;
    }
};