3723. Maximize Sum of Squares of Digits

Time: O(num)

Space: O(1)

Problem Overview

You need a number with exactly num digits whose digits add up to sum, and among those the one with the largest sum of squared digits, breaking ties by the larger number.

Intuition

You need a number with exactly num digits whose digits add up to sum, and among those the one with the largest sum of squared digits, breaking ties by the larger number. Squares reward big digits: moving one unit from a smaller digit to a larger one always raises the total of squares. So the best digits pack the sum into as many 9s as possible, then one leftover digit, then zeros. Writing the 9s first, then the leftover, then the zeros also gives the largest number with those digits.

Algorithm

1If num times 9 is less than sum, even all 9s cannot reach it, so return an empty string.
2Let nines be sum / 9 and rest be sum % 9.
3Write nines copies of 9 at the front of a string of length num.
4If rest is above 0, write that digit next.
5Fill the remaining positions with 0 and return the string.

Example Walkthrough

Input: num = 2, sum = 17

1.17 / 9 is 1 with remainder 8, so one 9 and then an 8.
2.No positions are left for zeros.
3.The squares add up to 81 + 64 = 145, more than any other two-digit split of 17.

Output: "98"

Common Pitfalls

•If sum is more than 9 times num, no answer exists, so return "".
•Do not append a 0 for the remainder. A zero remainder means the 9s already reach sum exactly.
•Putting zeros first would give a smaller number, and with leading zeros it would not even have num digits.
•Build the string in one buffer. Joining several temporary strings copies the digits more than once.

3723.cs

// Approach: For a fixed digit sum, squares grow fastest when the sum is packed
// into as few large digits as possible, so use as many 9s as fit, then the
// remainder digit, then zeros. Putting the large digits first also makes the
// number as large as possible. If even num 9s cannot reach sum, return "".
// The string is written once in place with string.Create.
// Time: O(num) Space: O(1) besides the output

public class Solution
{
    public string MaxSumOfSquares(int num, int sum)
    {
        if ((long)num * 9 < sum)
            return "";
        return string.Create(num, (nines: sum / 9, rest: sum % 9), static (span, s) =>
        {
            span[..s.nines].Fill('9');
            int i = s.nines;
            if (s.rest > 0)
                span[i++] = (char)('0' + s.rest);
            span[i..].Fill('0');
        });
    }
}

Was this solution helpful?