Even Digits – Google Kick Start Round A, 2018

Attempt 1

Following is my first submission, which did not pass.

T = int(input())

for t in range(T):
    isPlus = 1
    str_num = input()
    
    i = 0
    for i in range(len(str_num)):
        if i == len(str_num) - 1:
            if int(str_num[i]) % 2:
                isPlus = -1
            else:
                isPlus = -2
            break
        curr_digit = int(str_num[i]) 
        if curr_digit % 2:
            next_digit = int(str_num[i + 1])
            if next_digit < 5 or curr_digit == 9:
                # minus
                isPlus = 0
            break
            
    res = 0
    digits_left =  len(str_num) - i - 1
    current = int(str_num[i:])
    if isPlus == 1:
        target = int(str(int(str_num[i]) + 1) + '0' * digits_left)
        res = target - current
    elif isPlus == 0: # minus
        target = int(str(int(str_num[i]) - 1) + '8' * digits_left)
        res = current - target
    elif isPlus == -1: # even originally
        res = 1
    else:
        res = 0
        
    print('Case #{}: {}'.format(t + 1, res))
        

Attempt 2

I find the hint to be more complicated than mine, but it provides me a more systematic way to solve this problem.

I tried with this hint and tested every special case. It turned out that there are 2 special cases for the upper function. When there is a carry generated and when there is a series of carries ripple towards left. To solve that, I implemented the upper function in a recursive manner.

def upper(s):
    res = -1
    for i in range(len(s)):
        if int(s[i]) % 2 == 1:
            if i == 0 and s[i] == '9':
                res = int('10' + s[1:])
                break
            res = str(int('1' + (len(s) - i - 1) * '0') + int(s))
            res = int(res[:i+1] + (len(s) - i - 1) * '0')
            break
    if res == -1:
        return(int(s))
    else:
        return(upper(str(res)))

def lower(s):
    res = -1
    for i in range(len(s)):
        if int(s[i]) % 2 == 1:
            res = int(s[:i] + str(int(s[i]) - 1) + (len(s) - i - 1) * '8')
            break
    if res == -1:
        res = int(s)
    return res

# print(lower('4436271'))     # 4428888
# print(upper('4436271'))     # 4440000
# print(upper('86912'))       # 88000  
# print(upper('6488962'))     # 6600000
# print(upper('88892'))       # 200000
# print(upper('91112'))       # 200000

N  = int(input())
for n in range(N):
    sNum = input()
    intNum = int(sNum)
    l = intNum - lower(sNum)
    u = upper(sNum) - intNum
    res = l if l < u else u
    print("Case #{}: {}".format(n+1, res))

And it finally works!