In this Kata, 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`

More examples in the test cases.

Good luck!

Difficulty: introductory

Starter code:

def solve(n):
	

Solutions:
def solve(n):
    x = str(n)
    res = [x] + [str(int(x[:i]) - 1) + '9' * (len(x) - i) for i in range(1, len(x))]
    return int(max(res, key=lambda x: (sum(map(int, x)), int(x))))

def dig_sum(n):
    return sum(map(int, str(n)))

def solve(n):
    candidates = [n] + [ n // 10**i * 10**i - 1 for i in range(1, len(str(n))) ]
    return max(candidates, key=dig_sum)

from typing import List, Union
def digit_sum(n: Union[List[int], int]) -> int:
    """
    Finds the digit sum of the digits in an integer or list of positional integers
    """
    if isinstance(n, list):
        return sum(n)        
    return sum(int(ch) for ch in str(n))

def to_int(arr: List[int]) -> int:
    """
    Converts an array of positional integers into a single integer
    """
    return int(''.join(str(n) for n in arr))

def bump(arr, i):
    """
    Takes the digits of an array and increments the digit at index i and decrements the digit at 
    index i + 1.
    E.g. bump([1, 2, 8, 4], 1) -> [1, 2+1, 8-1, 4] -> [1, 3, 7, 4]
    """
    return arr[:i] + [arr[i] + 1] + [arr[i + 1] - 1] + arr[i+2:]

def solve(n: int) -> int:
    """
    Find the largest number <= n with the maximum digit sum
    """
    s = str(n)
    # Decrement the first digit and convert all others to 9 as a baseline
    option = [int(s[0]) - 1] + [9] * (len(s) - 1)
    if digit_sum(option) > digit_sum(n):
        for i in range(len(option) - 1):
            # Keep bumping digit i in option while still a single digit and the int value <= n
            while True:
                if option[i] == 9:
                    break
                b = bump(option, i)
                if to_int(b) > n:
                    break
                option = b
        return to_int(option)
    return n

def solve(n):
    s = str(n)
    l = len(s)
    if l == 1 or (l == 2 and s[1] in {"8", "9"}):
        return n
    for i in range(l-1):
        if s[i+1] != "9":
           return int(f"{s[:i]}{int(s[i]) - 1}{'9' * (l - i - 1)}")


def solve(n): return max([n]+[n-n%10**i-1 for i in range(len(str(n)))],key=lambda n:(sum(map(int,str(n))),n))

from math import log10, ceil

def solve(n):
    return max([n] + [n-n%10**x-1 for x in range(ceil(log10(n)))], key=lambda n: sum(map(int, str(n))))

solve=lambda n:(lambda s:int(max((str(int(s[:i])-(i<len(s)))+'9'*(len(s)-i)for i, d in enumerate(s,1)),key=lambda s:(sum(map(int,s)),s))))(str(n))


def solve(n):
    total = sum_digit(n)
    largest = n
    i = 1
    while n > 0:
        n = n - (n % (10)**i) -1
        print(n)
        new_total = sum_digit(n)
        i += 1
        if new_total > total:
            total = new_total
            largest = n
    return largest

def sum_digit(num):
    tot = 0
    while num > 0:
        tot += (num % 10)
        num = int(num /10)
    return tot 
        
        


def digit_sum(num):
    tot = 0
    while num > 0:
        tot += (num % 10)
        num = int(num /10)
    return tot 

def solve(n):
    total = digit_sum(n)
    largest = n
    print(n)
    i = 1
    while n > 0:
        n = n - (n % (10)**i) -1
        new_total = digit_sum(n)
        i += 1
        if new_total > total:
            total = new_total
            largest = n
    return largest

def solve(n):
    b = [int(str(n)[0]) - 1] + [9 for x in str(n)[1:]]
    digsum = sum(b)
    if digsum <= sum([int(x) for x in str(n)]):
        return n
    for i in range(len(str(n))-1, -1, -1):
        a = [int(x) for x in str(n)[:i]] + [int(str(n)[i]) - 1] + [9 for x in str(n)[i+1:]]
        print((i,a))
        if sum(a) == digsum:
            break
    return int("".join([str(x) for x in a]))