Largest Integer with a Maximum Digit-Square Score
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given positive integers `num` and `sum`. Consider positive integers with exactly `num` decimal digits whose digits add up to exactly `sum`.
An integer's score is the sum of the squares of its digits. Return the integer with the greatest score as a string. If several integers share that maximum score, return the numerically greatest one. If no integer satisfies the length and digit-sum conditions, return an empty string.
```cpp
class Solution {
public:
string maxSumOfSquares(int num, int sum);
};
```
### Examples
**Example 1:**
```text
Input: num = 3, sum = 20
Output: "992"
Explanation: Its digit sum is 20 and its score is 81+81+4 = 166, the maximum attainable score. The equal-score arrangements "929" and "299" are smaller, so "992" wins the numeric tie-break.
```
**Example 2:**
```text
Input: num = 4, sum = 1
Output: "1000"
Explanation: A positive four-digit integer with digit sum one must be 1000. Its score is one. Leading-zero strings do not represent four-digit integers.
```
### Constraints
- `1 <= num <= 200000`.
- `1 <= sum <= 2000000`.
### Clarifying Questions
- Are the digit count and digit sum exact requirements? Yes.
- May zeros occur after the first digit? Yes.
- May the representation begin with zero? No; it must denote a positive integer with exactly `num` digits.
- Is the score itself returned? No. Return the selected integer's decimal string, using the numeric tie-break if needed.
### What a Strong Answer Covers
- Feasibility, exact digit count, exact digit sum, and positive-integer representation.
- A proof of maximum squared-digit score and the required largest-integer tie-break.
- Small sums, impossible inputs, and large output lengths.
- Resource bounds that account for constructing the returned string.
### Follow-up Questions
- Why is a string needed for the largest allowed digit counts?
- How could requesting every maximum-score integer affect output size?
```hint Compare a one-unit transfer
Consider moving one unit of digit sum from a smaller positive digit to a larger digit that is still below nine. Compare the squared-digit scores, then decide how to order a maximum-score multiset for the numeric tie-break.
```
Overview: Construct the greatest maximum-score integer with an exact digit count and sum. Covers squared-digit scoring, feasibility, ties, proof, and C++ code.