3723. Maximize Sum of Squares of Digits

Difficulty: Medium

Topics: Staff, Math, Greedy, Biweekly Contest 168

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 "".

Example 4:

  • Input: num = 1, sum = 9
  • Output: "9"
  • Explanation: The only possible digit is 9.

Example 5:

  • Input: num = 2, sum = 18
  • Output: "99"
  • Explanation: The maximum digit sum for 2 digits is 9 + 9 = 18, so the only valid integer is 99.

Example 6:

  • Input: num = 3, sum = 18
  • Output: "990"
  • Explanation: To maximize the score, use two 9s and one 0: 9² + 9² + 0² = 162. The maximum valid integer is 990.

Example 7:

  • Input: num = 3, sum = 19
  • Output: "991"
  • Explanation: The best digits are two 9s and one 1: 9² + 9² + 1² = 163. The maximum valid integer is 991.

Example 8:

  • Input: num = 3, sum = 27
  • Output: "999"
  • Explanation: The maximum digit sum for 3 digits is 9 + 9 + 9 = 27, so the only valid integer is 999.

Example 9:

  • Input: num = 3, sum = 28
  • Output: ""
  • Explanation: The maximum digit sum for 3 digits is 9 * 3 = 27, so sum 28 is impossible.

Example 10:

  • Input: num = 4, sum = 1
  • Output: "1000"
  • Explanation: The only valid 4-digit integer with digit sum 1 is 1000.

Example 11:

  • Input: num = 2, sum = 10
  • Output: "91"
  • Explanation: The maximum score is 9² + 1² = 82, achieved by both 19 and 91. The maximum valid integer is 91.

Example 12:

  • Input: num = 5, sum = 45
  • Output: "99999"
  • Explanation: The maximum digit sum for 5 digits is 9 * 5 = 45, so the only valid integer is 99999.

Constraints:

  • 1 <= num <= 2 * 10⁵
  • 1 <= sum <= 2 * 10⁶

Hint:

  1. Use a greedy approach.
  2. Fill the leftmost digits with 9s first (as much as possible).

Solution:

We need to handle two types of queries on a power grid where stations can go offline, and I need to find the smallest operational station in the same connected component.

Approach

  • Let num be the required number of digits and sum be the required digit sum.
  • If sum > 9 * num, it is impossible to form such a number, so return "".
  • Compute:
    • q = intdiv(sum, 9) — number of 9s we can use.
    • r = sum % 9 — leftover digit after placing 9s.
  • If r == 0, return q copies of '9' followed by num - q copies of '0'.
  • Otherwise, return q copies of '9', then r, then enough '0's to reach exactly num digits.
  • This construction is valid because the first digit is never 0 when sum > 0.

Let's implement this solution in PHP: 3723. Maximize Sum of Squares of Digits

<?php /** * @param Integer $num * @param Integer $sum * @return String */ function maxSumOfSquares(int $num, int $sum): string { ... ... ... /** * go to ./solution.php */ } // Test cases echo maxSumOfSquares(2, 3) . "\n"; // Output: "30" echo maxSumOfSquares(2, 17) . "\n"; // Output: "98" echo maxSumOfSquares(1, 10) . "\n"; // Output: "" echo maxSumOfSquares(1, 9) . "\n"; // Output: "9" echo maxSumOfSquares(2, 18) . "\n"; // Output: "99" echo maxSumOfSquares(3, 18) . "\n"; // Output: "990" echo maxSumOfSquares(3, 19) . "\n"; // Output: "991" echo maxSumOfSquares(3, 27) . "\n"; // Output: "999" echo maxSumOfSquares(3, 28) . "\n"; // Output: "" echo maxSumOfSquares(4, 1) . "\n"; // Output: "1000" echo maxSumOfSquares(2, 10) . "\n"; // Output: "91" echo maxSumOfSquares(5, 45) . "\n"; // Output: "99999" ?>

Explanation:

  • To maximize sum of squares, we want digits to be as large and unequal as possible.
  • The largest allowed digit is 9, so we use as many 9s as possible.
  • Any remaining sum less than 9 becomes a single digit.
  • The remaining positions must be 0 because they do not change the digit sum and preserve the required number of digits.
  • Ordering digits as 9...9 r 0...0 gives the largest possible integer among all numbers with the same maximum score.
  • Example: num = 2, sum = 17 gives q = 1, r = 8, so the answer is "98".

Complexity Analysis

  • Time Complexity: O(num) because we build a string of length num.
  • Space Complexity: O(num) for the returned string.
  • Auxiliary Space: O(1) excluding the output string.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
Buy Me A Coffee

If you want more helpful content like this, feel free to follow me: