October 14Medium

Maximize sum of squares of digits

Math
Greedy

Problem

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.

Solution

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        res = ""

        if num * 9 < sum:
            return res

        for i in range(num):
            s = min(sum, 9)
            sum -= s
            res += str(s)

        return res