Max Digit Sum Number in 1 to n

Problem Overview

Digit sum grows when low digits become 9s.

Intuition

Digit sum grows when low digits become 9s. From n, the useful rivals are formed by cutting one digit by one and filling every digit to its right with 9. Compare those few candidates with n; take the largest digit sum, and on a tie take the bigger number.

Algorithm

1Start with result = n and maxSum = digitSum(n).
2Set temp = n and multiplier = 1.
3While temp is positive, build candidate = (temp - 1) * multiplier + (multiplier - 1).
4If its digit sum is better, or equal with a larger value, update result.
5Divide temp by 10 and multiply the multiplier by 10.
6Return result.

Example Walkthrough

Input: n = 521

1. Candidates include 521, 520, 519, and 499.
2. Digit sums are 8, 7, 15, and 22.
3. 499 wins with the maximum digit sum.

Output: 499

Common Pitfalls

• Do not scan all of 1..n; only the digit-flip candidates matter.
• On equal digit sums, prefer the larger integer.
• Single-digit n is already optimal; return it immediately.
• The formula (temp - 1) * 10^k + (10^k - 1) writes all 9s on the right.

Max Digit Sum Number in 1 to n.java

Java

// Approach: Among 1..n, max digit sum is achieved by n or by decreasing one
// digit and setting all digits to its right to 9. Try each such candidate and
// keep the best sum, breaking ties with the larger value.
// Complexity: O(d^2) time and O(1) extra space, d = number of digits.
class Solution {

    public int findMax(int n) {
        if (n <= 9) {
            return n;
        }

        long maxSum = digitSum(n);
        int result = n;

        long temp = n;
        long multiplier = 1;

        while (temp > 0) {
            long candidate = (temp - 1) * multiplier + (multiplier - 1);
            long currentSum = digitSum(candidate);

            if (currentSum > maxSum || (currentSum == maxSum && candidate > result)) {
                maxSum = currentSum;
                result = (int) candidate;
            }

            temp /= 10;
            multiplier *= 10;
        }

        return result;
    }

    private long digitSum(long n) {
        long sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}

Was this solution helpful?