Skip to content

3723. Maximize Sum of Squares of Digits

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 12 + 22 = 5.
  • The score of 21 is 22 + 12 = 5.
  • The score of 30 is 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.

  • The score of 89 is 82 + 92 = 145.
  • The score of 98 is 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 * 105
  • 1 <= sum <= 2 * 106

Solutions

Solution 1: Greedy

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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 += digits[s]
        ans += "0" * (num - len(ans))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

Comments