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:

 ``````1 2 3 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 `````` ``````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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````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)); } } ``````