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!