3723. Maximize Sum of Squares of Digits

SourceBiweekly Contest 168 Q2DifficultyMediumRating1536

Description

You are given two positive integers num and sum.

A positive integer n is good if it satisfies both of the following:

The number of digits in n is exactly num.
The sum of digits in 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.

The score of 12 is 1² + 2² = 5.
The score of 21 is 2² + 1² = 5.
The score of 30 is 3² + 0² = 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.

The score of 89 is 8² + 9² = 145.
The score of 98 is 9² + 8² = 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 * 10⁵
1 <= sum <= 2 * 10⁶

Solutions

Solution 1: Greedy

Thinking

Enumerating every \(\text{num}\)-digit integer whose digits sum to \(\text{sum}\) and then comparing scores cannot finish when \(\text{num}\) reaches \(2\times 10^5\). The candidate set grows exponentially with the length, and the score still depends on how the digits are spread out, so the comparison itself is the bottleneck. Squaring is convex on the non-negative integers, so a fixed sum produces a larger sum of squares when the digits are concentrated; the optimal multiset is therefore as many \(9\)s as possible plus at most one remainder. Writing those larger digits from the high end leaves the score unchanged and selects the numerically largest integer among ties, which is why the answer is assembled directly in that order.

If \(\text{num} \times 9 < \text{sum}\), then there is no valid good integer, so we return an empty string.

Otherwise, we can use as many digits \(9\) as possible to form the good integer, since \(9^2\) is the largest and will maximize the score. Specifically, we calculate how many \(9\)s are contained in \(\text{sum}\), denoted as \(k\), and the remaining part \(s = \text{sum} - 9 \times k\). Then, we construct the good integer with the first \(k\) digits as \(9\). If \(s > 0\), we append a digit \(s\) at the end, and finally pad with \(0\)s to reach a total of \(\text{num}\) digits.

The time complexity is \(O(\text{num})\) and the space complexity is \(O(\text{num})\), where \(\text{num}\) is the number of digits in the good integer.

Python3JavaC++GoTypeScriptRustC#JavaScript

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        if num * 9 < sum:
            return ""
        k, s = divmod(sum, 9)
        ans = "9" * k
        if s:
            ans += str(s)
        ans += "0" * (num - len(ans))
        return ans

class Solution {
    public String maxSumOfSquares(int num, int sum) {
        if (num * 9 < sum) {
            return "";
        }
        int k = sum / 9;
        sum %= 9;
        StringBuilder ans = new StringBuilder("9".repeat(k));
        if (sum > 0) {
            ans.append(sum);
        }
        ans.append("0".repeat(num - ans.length()));
        return ans.toString();
    }
}

class Solution {
public:
    string maxSumOfSquares(int num, int sum) {
        if (num * 9 < sum) {
            return "";
        }
        int k = sum / 9, s = sum % 9;
        string ans(k, '9');
        if (s > 0) {
            ans += char('0' + s);
        }
        ans += string(num - ans.size(), '0');
        return ans;
    }
};

func maxSumOfSquares(num int, sum int) string {
    if num*9 < sum {
        return ""
    }

    k, s := sum/9, sum%9
    ans := strings.Repeat("9", k)
    if s > 0 {
        ans += string('0' + byte(s))
    }
    if len(ans) < num {
        ans += strings.Repeat("0", num-len(ans))
    }

    return ans
}

function maxSumOfSquares(num: number, sum: number): string {
    if (num * 9 < sum) {
        return '';
    }

    const k = Math.floor(sum / 9);
    const s = sum % 9;

    let ans = '9'.repeat(k);
    if (s > 0) {
        ans += String.fromCharCode('0'.charCodeAt(0) + s);
    }
    if (ans.length < num) {
        ans += '0'.repeat(num - ans.length);
    }

    return ans;
}

impl Solution {
    pub fn max_sum_of_squares(num: i32, sum: i32) -> String {
        if num * 9 < sum {
            return String::new();
        }
        let k = sum / 9;
        let s = sum % 9;
        let mut ans = "9".repeat(k as usize);
        if s > 0 {
            ans.push((b'0' + s as u8) as char);
        }
        if ans.len() < num as usize {
            ans.push_str(&"0".repeat(num as usize - ans.len()));
        }
        ans
    }
}

public class Solution {
    public string MaxSumOfSquares(int num, int sum) {
        if (num * 9 < sum) {
            return "";
        }
        int k = sum / 9;
        int s = sum % 9;
        var ans = new StringBuilder(num);
        ans.Append('9', k);
        if (s > 0) {
            ans.Append(s);
        }
        ans.Append('0', num - ans.Length);
        return ans.ToString();
    }
}

/**
 * @param {number} num
 * @param {number} sum
 * @return {string}
 */
var maxSumOfSquares = function (num, sum) {
    if (num * 9 < sum) {
        return '';
    }
    const k = Math.floor(sum / 9);
    const s = sum % 9;
    let ans = '9'.repeat(k);
    if (s > 0) {
        ans += String.fromCharCode('0'.charCodeAt(0) + s);
    }
    if (ans.length < num) {
        ans += '0'.repeat(num - ans.length);
    }
    return ans;
};

3723. Maximize Sum of Squares of Digits

Description

Solutions

Solution 1: Greedy

Comments