Maximum Digit Sum in Java: Algorithm, Examples & Dry Run

Problem Statement

Given an integer n, find a number in the range from 1 to n whose digit sum is maximum.

If multiple numbers have the same maximum digit sum, return the largest number among them.

Example 1

Input: n = 48
Output: 48

The digit sums of the relevant numbers are:

Digit sum of 48 = 4 + 8 = 12
Digit sum of 39 = 3 + 9 = 12

Both numbers have the same maximum digit sum, but:

48 > 39

Therefore, the answer is:

Example 2

Input: n = 90
Output: 89

Because:

Digit sum of 90 = 9 + 0 = 9
Digit sum of 89 = 8 + 9 = 17

Therefore, the answer is:

Approach

A simple solution would be to check every number from 1 to n, calculate its digit sum, and keep track of the best answer.

However, this becomes inefficient when n is large.

For example, if:

n = 1,000,000,000

checking every number would require a very large number of operations.

Instead, we can use an important observation about decimal numbers.

Key Observation

For any candidate smaller than n, the best way to maximize its digit sum is to:

Choose a non-zero digit of n.
Decrease that digit by 1.
Replace every digit to its right with 9.
Keep the digits to its left unchanged.

Why does this work?

The digit 9 provides the largest possible contribution to a decimal digit sum. Therefore, after making a number smaller at one position, setting every following digit to 9 gives the maximum possible digit sum for that prefix.

For example:

n = 1234

Possible candidates generated from n include:

Their digit sums are:

1234 → 1 + 2 + 3 + 4 = 10
1229 → 1 + 2 + 2 + 9 = 14
1199 → 1 + 1 + 9 + 9 = 20
999  → 9 + 9 + 9 = 27

So the best candidate is:

Example: n = 48

Start with:

n = 48

The digit sum is:

4 + 8 = 12

Now consider the tens digit.

Decrease:

4 → 3

and replace everything to its right with 9:

48
↓
39

The digit sum of 39 is:

3 + 9 = 12

We now have:

48 → 12
39 → 12

Both have the same digit sum, so we select the larger number:

Example: n = 90

Start with:

n = 90

Its digit sum is:

9 + 0 = 9

The last digit is 0, so it cannot be decreased.

Now consider the first digit:

9 → 8

Replace the digit to its right with 9:

90
↓
89

The digit sum becomes:

8 + 9 = 17

Therefore:

is better than 90.

Java Implementation

class Solution {

    public int findMax(int n) {
        int best = n;
        int maxSum = digitSum(n);

        int temp = n;
        int place = 1;

        while (temp > 0) {
            int digit = temp % 10;

            if (digit > 0) {
                int candidate =
                        (n / (place * 10)) * (place * 10)
                        + (digit - 1) * place
                        + (place - 1);

                int sum = digitSum(candidate);

                if (sum > maxSum ||
                    (sum == maxSum && candidate > best)) {
                    maxSum = sum;
                    best = candidate;
                }
            }

            temp /= 10;
            place *= 10;
        }

        return best;
    }

    private int digitSum(int num) {
        int sum = 0;

        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }

        return sum;
    }
}

Code Explanation

1. Initialize the Answer

The first step is to consider n itself as a candidate.

int best = n;
int maxSum = digitSum(n);

For:

n = 48

we get:

best = 48
maxSum = 12

This is important because n itself can be the answer, as demonstrated by the n = 48 example.

2. Process Each Digit

The following variables are used to process the digits:

int temp = n;
int place = 1;

Then:

while (temp > 0) {
    int digit = temp % 10;

The expression:

temp % 10

extracts the rightmost digit.

For example, if:

n = 1234

the digits are processed in this order:

The place variable represents the position of the current digit:

1     → units
10    → tens
100   → hundreds
1000  → thousands

3. Ignore Zero Digits

The code checks:

if (digit > 0) {

A digit must be greater than zero because the algorithm decreases it by one.

For example:

5 → 4

is valid.

But:

0 → -1

is not valid.

Therefore, zero digits are skipped.

4. Construct the Candidate

The most important part of the algorithm is:

int candidate =
        (n / (place * 10)) * (place * 10)
        + (digit - 1) * place
        + (place - 1);

This constructs a candidate with three parts:

Original digits to the left
          +
Current digit decreased by 1
          +
All digits to the right changed to 9

Example: n = 548

Suppose we select the hundreds digit:

Decrease it:

5 → 4

and replace the remaining digits with 9:

548
↓
499

The candidate is:

Its digit sum is:

4 + 9 + 9 = 22

Another Example: n = 527

If we select the tens digit:

2 → 1

and replace the digit to its right with 9:

527
↓
519

So 519 becomes one of the candidates considered by the algorithm.

5. Calculate the Candidate's Digit Sum

After creating a candidate, calculate its digit sum:

int sum = digitSum(candidate);

The helper method is:

private int digitSum(int num) {
    int sum = 0;

    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }

    return sum;
}

For example, for:

num = 499

the method performs:

499 % 10 = 9
49  % 10 = 9
4   % 10 = 4

Therefore:

digit sum = 9 + 9 + 4
          = 22

6. Update the Best Answer

The candidate is selected when either of these conditions is true:

if (sum > maxSum ||
    (sum == maxSum && candidate > best)) {
    maxSum = sum;
    best = candidate;
}

Condition 1: Larger Digit Sum

sum > maxSum

If the candidate has a larger digit sum, it becomes the new answer.

For example:

Current best = 90
Digit sum = 9

Candidate = 89
Digit sum = 17

Because:

17 > 9

the candidate 89 becomes the new answer.

Condition 2: Same Digit Sum, Larger Number

sum == maxSum && candidate > best

This handles the tie-breaking rule.

For example:

39 → digit sum = 12
48 → digit sum = 12

Both have the same digit sum, but:

48 > 39

Therefore, 48 must be selected.

7. Move to the Next Digit

At the end of each iteration:

temp /= 10;
place *= 10;

For example:

temp:

548
 ↓
54
 ↓
5
 ↓
0

At the same time:

place:

1
 ↓
10
 ↓
100
 ↓
1000

This allows the algorithm to inspect every digit.

Digit Sum Function

The digitSum() method repeatedly extracts the last digit.

private int digitSum(int num) {
    int sum = 0;

    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }

    return sum;
}

For example:

Input: 123

Execution:

123 % 10 = 3
12  % 10 = 2
1   % 10 = 1

Therefore:

Digit sum = 3 + 2 + 1
          = 6

Dry Run: n = 90

Let's walk through the algorithm.

Initial values:

n = 90
best = 90
maxSum = 9

First Iteration

The current digit is:

Since:

0 > 0

is false, this digit is skipped.

Second Iteration

The current digit is:

Create the candidate:

Calculate its digit sum:

8 + 9 = 17

Compare:

17 > 9

So:

best = 89
maxSum = 17

The final result is:

Dry Run: n = 48

Initial values:

n = 48
best = 48
maxSum = 12

The candidate generated by decreasing the tens digit is:

Its digit sum is:

3 + 9 = 12

Now compare:

candidate sum = 12
maximum sum   = 12

The sums are equal.

Next, compare the numbers:

39 < 48

Therefore, best remains:

The final result is:

Why Does This Approach Work?

Suppose we want to create a number smaller than n.

At some position, we must make the number smaller than n. The best way to maximize the digit sum after doing that is to make every digit to the right equal to 9.

For example:

n = 527

If the first digit is reduced:

527
↓
499

If the second digit is reduced:

527
↓
519

We also consider n itself:

Therefore, the relevant candidates are:

527
519
499

We calculate their digit sums and select the candidate with the largest sum. If two candidates have the same sum, the larger candidate is selected.

This means we do not need to inspect every number from 1 to n.

Complexity Analysis

Let d be the number of digits in n.

The algorithm processes each digit once. However, for every candidate it calls digitSum(), which itself takes O(d) time.

Therefore, the implementation shown above has:

Time Complexity: O(d²)
Auxiliary Space: O(1)

Because an integer has only a limited number of digits for normal integer constraints, this is effectively very small in practice.

If n is restricted to values up to 10^9, then d is at most 10.

The candidate generation itself is O(d), while the repeated digit-sum calculation makes the complete implementation O(d²).

Important Takeaway

The key observation is:

To maximize the digit sum of a number less than or equal to n, decrease one non-zero digit of n by 1 and replace every digit after it with 9.

Always include n itself because it may already have the maximum digit sum.

The overall strategy is:

Start with n
     ↓
Process each non-zero digit
     ↓
Decrease that digit by 1
     ↓
Replace following digits with 9
     ↓
Calculate digit sum
     ↓
Compare with current best
     ↓
Apply largest-number tie-breaker
     ↓
Return best

This turns what initially looks like a brute-force problem into a digit-based optimization problem that requires checking only a small number of candidates.