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

Code

Input: n = 48
Output: 48

The digit sums of the relevant numbers are:

Code

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

Both numbers have the same maximum digit sum, but:

Code

48 > 39

Therefore, the answer is:

Code

Example 2

Code

Input: n = 90
Output: 89

Because:

Code

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

Therefore, the answer is:

Code

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:

Code

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:

Code

n = 1234

Possible candidates generated from n include:

Code

Their digit sums are:

Code

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:

Code

Example: n = 48

Start with:

Code

n = 48

The digit sum is:

Code

4 + 8 = 12

Now consider the tens digit.

Decrease:

Code

4 → 3

and replace everything to its right with 9:

Code

48
↓
39

The digit sum of 39 is:

Code

3 + 9 = 12

We now have:

Code

48 → 12
39 → 12

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

Code

Example: n = 90

Start with:

Code

n = 90

Its digit sum is:

Code

9 + 0 = 9

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

Now consider the first digit:

Code

9 → 8

Replace the digit to its right with 9:

Code

90
↓
89

The digit sum becomes:

Code

8 + 9 = 17

Therefore:

Code

is better than 90.

Java Implementation

Java

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.

Java

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

For:

Code

n = 48

we get:

Code

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:

Java

int temp = n;
int place = 1;

Then:

Java

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

The expression:

Java

temp % 10

extracts the rightmost digit.

For example, if:

Code

n = 1234

the digits are processed in this order:

Code

The place variable represents the position of the current digit:

Code

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

3. Ignore Zero Digits

The code checks:

Java

if (digit > 0) {

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

For example:

Code

5 → 4

is valid.

But:

Code

0 → -1

is not valid.

Therefore, zero digits are skipped.

4. Construct the Candidate

The most important part of the algorithm is:

Java

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

This constructs a candidate with three parts:

Code

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:

Code

Decrease it:

Code

5 → 4

and replace the remaining digits with 9:

Code

548
↓
499

The candidate is:

Code

Its digit sum is:

Code

4 + 9 + 9 = 22

Another Example: n = 527

If we select the tens digit:

Code

2 → 1

and replace the digit to its right with 9:

Code

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:

Java

int sum = digitSum(candidate);

The helper method is:

Java

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

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

    return sum;
}

For example, for:

Code

num = 499

the method performs:

Code

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

Therefore:

Code

digit sum = 9 + 9 + 4
          = 22

6. Update the Best Answer

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

Java

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

Condition 1: Larger Digit Sum

Java

sum > maxSum

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

For example:

Code

Current best = 90
Digit sum = 9

Candidate = 89
Digit sum = 17

Because:

Code

17 > 9

the candidate 89 becomes the new answer.

Condition 2: Same Digit Sum, Larger Number

Java

sum == maxSum && candidate > best

This handles the tie-breaking rule.

For example:

Code

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

Both have the same digit sum, but:

Code

48 > 39

Therefore, 48 must be selected.

7. Move to the Next Digit

At the end of each iteration:

Java

temp /= 10;
place *= 10;

For example:

Code

temp:

548
 ↓
54
 ↓
5
 ↓
0

At the same time:

Code

place:

1
 ↓
10
 ↓
100
 ↓
1000

This allows the algorithm to inspect every digit.

Digit Sum Function

The digitSum() method repeatedly extracts the last digit.

Java

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

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

    return sum;
}

For example:

Code

Input: 123

Execution:

Code

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

Therefore:

Code

Digit sum = 3 + 2 + 1
          = 6

Dry Run: n = 90

Let's walk through the algorithm.

Initial values:

Code

n = 90
best = 90
maxSum = 9

First Iteration

The current digit is:

Code

Since:

Code

0 > 0

is false, this digit is skipped.

Second Iteration

The current digit is:

Code

Create the candidate:

Code

Calculate its digit sum:

Code

8 + 9 = 17

Compare:

Code

17 > 9

So:

Code

best = 89
maxSum = 17

The final result is:

Code

Dry Run: n = 48

Initial values:

Code

n = 48
best = 48
maxSum = 12

The candidate generated by decreasing the tens digit is:

Code

Its digit sum is:

Code

3 + 9 = 12

Now compare:

Code

candidate sum = 12
maximum sum   = 12

The sums are equal.

Next, compare the numbers:

Code

39 < 48

Therefore, best remains:

Code

The final result is:

Code

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:

Code

n = 527

If the first digit is reduced:

Code

527
↓
499

If the second digit is reduced:

Code

527
↓
519

We also consider n itself:

Code

Therefore, the relevant candidates are:

Code

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:

Code

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:

Code

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.