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

Thinking

With a fixed digit sum, the sum of squares is maximized by using as many \(9\)s as possible. If \(9\times num<sum\) there is no solution; otherwise we write as many \(9\)s as we can, place the remainder in the next digit, and pad with zeros to length \(num\), which also yields the numerically largest such integer.

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