Calculating Simple Max Digit Sum in Java

The challenge

In this challenge, you will be given an integer n and your task will be to return the largest integer that is <= n and has the highest digit sum.

For example:

solve(100) = 99. Digit Sum for 99 = 9 + 9 = 18. No other number <= 100 has a higher digit sum.
solve(10) = 9
solve(48) = 48. Note that 39 is also an option, but 48 is larger.

Input range is 0 < n < 1e11

The solution in Java code

Option 1:

class Solution{    
  public static long solve(long n) {
    if (n < 10)
      return n;
    long m = n, e = 1;
    do {
      m /= 10;
      e *= 10;
    } while (m >= 10);
    long t = m * e + (e - 1);
    for (e = 1; ; e *= 10)
      if (t - e <= n)
        return t - e;
  }
}

Option 2:

class Solution{    
    public static long solve(long n) {
        if (n > 0) {
            int nLength = String.valueOf(n).chars().map(a -> 1).sum();
            int sum = 0;
            int[] digits = new int[nLength];
            for (int i = 0; i < nLength; i++) {
                digits[i] = Character.getNumericValue(String.valueOf(n).charAt(i));
                sum += digits[i];
            }
            if (sum >= (digits[0] - 1) + ((nLength - 1) * 9)) {
                return n;
            }
            if (digits[1] < 9) {
                digits[0]--;
                String result = String.valueOf(digits[0]);
                for (int i = 0; i < nLength - 1; i++) {
                    result = result + 9;
                }
                return Long.valueOf(result);
            }
            for (int i = 1; i < digits.length; i++) {
                if (digits[i] == 9 && digits[i + 1] < 9) {
                    digits[i] = 8;
                    for (int j = i + 1; j < digits.length; j++) {
                        digits[j] = 9;
                    }
                    String result = "";
                    for (int k = 0; k < digits.length; k++) {
                        result = result + digits[k];
                    }
                    return Long.valueOf(result);
                }
            }
        }
        return 0;
    }

}

Option 3:

class Solution{    
  
  public static long solve(long n) { 
        long b = 1, ans = n; 
        while (n!=0) { 
            long cur = (n - 1) * b + (b - 1); 
            long curSumOFDigits = sumOfDigits(cur);
            long ansSumOfDigits = sumOfDigits(ans);
            if (curSumOFDigits > ansSumOfDigits || (curSumOFDigits == ansSumOfDigits && cur > ans)) {
               ans = cur; 
            }   
            n /= 10; 
            b *= 10; 
        } 
        return ans; 
    } 
  
    private static long sumOfDigits(long a) { 
        long sum = 0; 
        while (a!=0) { 
            sum += a % 10; 
            a /= 10; 
        } 
        return sum; 
    } 
}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest{    
    @Test
    public void basicTests(){     
        assertEquals(1L,Solution.solve(1L));
        assertEquals(2L,Solution.solve(2L));
        assertEquals(18L,Solution.solve(18L));
        assertEquals(48L,Solution.solve(48L));
        assertEquals(99L,Solution.solve(100L));
        assertEquals(9L,Solution.solve(10L));
        assertEquals(99L,Solution.solve(110L));
        assertEquals(1999L,Solution.solve(2090L));
        assertEquals(999999999989L,Solution.solve(999999999992L));
    }
}
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments