Maximize sum of squares of digits

Math Greedy

58.9% acceptance

Feb 24, 2026

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

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_of_squares(num: i32, sum: i32) -> String {
    let num = num as usize;
    let sum = sum as usize;
    // Max sum of squares: use as many 9s as possible, then remainder, then zeros
    // But also need to maximize the number (same score -> larger number preferred)
    // Max score: fill with nines from left, remainder, zeros
    if sum > 9 * num { return String::new(); }
    let mut digits = Vec::with_capacity(num);
    let mut rem = sum;
    for _ in 0..num {
      let d = rem.min(9);
      digits.push(d as u8);
      rem -= d;
    }
    // digits is sorted descending already (9s first, then remainder, then 0s)
    // This gives maximum score AND maximum number
    String::from_utf8(digits.iter().map(|&d| b'0' + d).collect()).unwrap()
  }
}