Skip to main content
Talentd

Maximize Sum of Squares of Digits - Solution & Explanation

MediumMathGreedy7 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You need to maximize the total sum(digit^2) formed from a set or representation of digits while preserving the overall numeric constraints (such as total digit sum or allowed transformations). The challenge comes from the fact that squaring favors larger digits, so the distribution of values across digits directly affects the final score.

Approach 1: Greedy Digit Maximization (O(n) time, O(1) space)

The key mathematical insight is that the square function is convex. Moving value from a smaller digit to a larger digit increases the total sum of squares. For example, 1^2 + 5^2 = 26 while 0^2 + 6^2 = 36. Because of this property, the optimal strategy is to concentrate as much value as possible into the largest digits. A greedy approach repeatedly assigns the maximum possible digit value (usually 9) while maintaining the required total digit sum or constraint.

Implementation is straightforward: iterate while there is remaining digit value to distribute. At each step, assign min(9, remaining_sum) to the next digit and subtract it from the remaining total. Each assignment contributes digit * digit to the final score. This greedy allocation ensures the largest digits receive the most value, which maximizes the squared contribution.

This works because any redistribution that moves value from a larger digit to a smaller one reduces the sum of squares. The greedy strategy therefore produces a globally optimal configuration without backtracking or dynamic programming. The algorithm simply processes digits sequentially and performs constant-time arithmetic operations.

Problems like this often appear under greedy and math categories because the optimal solution depends on recognizing the convex behavior of the square function rather than exploring combinations. You iterate through the digits once and maintain a running total.

Recommended for interviews: Interviewers expect the greedy reasoning. A brute-force search over all digit distributions grows exponentially and is unnecessary once you recognize the convex property of squares. Explaining why concentrating value into larger digits increases the objective demonstrates strong mathematical intuition and familiarity with greedy algorithms.

Solution

If num times 9 < 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 9s are contained in sum, denoted as k, and the remaining part s = 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 0s to reach a total of num digits.

The time complexity is O(num) and the space complexity is O(num), where num is the number of digits in the good integer.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Digit DistributionExponentialO(n)Conceptual baseline when exploring all digit allocations
Greedy Digit MaximizationO(n)O(1)Optimal approach when maximizing squared digit contribution

Video Solution

Leetcode in Distress (┬┬﹏┬┬) | Maximize Sum of Squares of Digits | Biweekly 168 β€’ so-um-ya β€’ 963 views views

Watch 7 more video solutions β†’

Frequently Asked Questions

Is Maximize Sum of Squares of Digits easy or hard?
This problem is typically classified as Medium difficulty. The implementation is simple, but recognizing the greedy insight that concentrating value into larger digits increases the total squared contribution is the key step.
Maximize Sum of Squares of Digits Python/Java solution
The implementation is identical across languages. Maintain a remaining digit sum, repeatedly assign min(9, remaining_sum), add digit * digit to the result, and subtract the assigned value. This logic translates directly to Python, Java, C++, Go, or TypeScript.
How to solve Maximize Sum of Squares of Digits in O(n)?
Iterate through the digits while maintaining the remaining total value that can be assigned. At each step assign the maximum allowed digit value, typically min(9, remaining_sum), then subtract it from the remaining amount. Add digit^2 to the result. This greedy allocation maximizes squared contributions and finishes in linear time.
What is the best approach for Maximize Sum of Squares of Digits?
The optimal approach is a greedy strategy based on the convex property of the square function. Larger digits contribute disproportionately more when squared, so concentrating value into the largest possible digits maximizes the result. The algorithm iteratively assigns the largest valid digit (often 9) until the remaining value is exhausted. This runs in O(n) time with O(1) space.
Is Maximize Sum of Squares of Digits asked at Google/Amazon/Meta?
Greedy math optimization problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. They test whether candidates recognize mathematical properties such as convexity and can justify why a greedy distribution leads to the global optimum.
What data structure is used in Maximize Sum of Squares of Digits?
No complex data structures are required. The solution relies on simple integer variables and iteration. The core idea is mathematical optimization rather than using structures like heaps or hash maps.
What is the time complexity of Maximize Sum of Squares of Digits?
The greedy solution runs in O(n) time, where n is the number of digits processed or generated. Each step performs constant-time arithmetic and reduces the remaining value. Space complexity is O(1) because only a few variables are needed to track the remaining sum and accumulated result.

Ready to solve this problem?

Practice Maximize Sum of Squares of Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer