Palindromic Numbers  (Codeforces 1700B)
Tags: Math, implementation

During a daily walk Alina noticed a long number written on the ground. Now Alina wants to find some positive number of same length without leading zeroes, such that the sum of these two numbers is a palindrome. Recall that a number is called a palindrome, if it reads the same right to left and left to right. For example, numbers $$$121, 66, 98989$$$ are palindromes, and $$$103, 239, 1241$$$ are not palindromes.Alina understands that a valid number always exist. Help her find one!

Input: The first line of input data contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Next, descriptions of $$$t$$$ test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — the length of the number that is written on the ground.The second line of contains the positive $$$n$$$-digit integer without leading zeroes — the number itself.It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

Output: For each of $$$t$$$ test cases print an answer — a positive $$$n$$$-digit integer without leading zeros, such that the sum of the input integer and this number is a palindrome.We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them.

Note: In the first test case $$$99 + 32 = 131$$$ is a palindrome. Note that another answer is $$$12$$$, because $$$99 + 12 = 111$$$ is also a palindrome.In the second test case $$$1023 + 8646 = 9669$$$.In the third test case $$$385 + 604 = 989$$$.

Sample Inputs:
3
2
99
4
1023
3
385

Sample Outputs:
32
8646
604

Solution (Python):
def solve():
    n = int(input())
    s = input()
    res = [''] * n
    ascii_9 = ord('9')
    ascii_1 = ord('1')
    ascii_0 = ord('0')
    if s[0] == '9':
        is_borrowed = False
        for i in range(n - 1, -1, -1):
            num = 0
            ascii_i = ord(s[i])
            if not is_borrowed:
                if ascii_1 >= ascii_i:
                    num = ascii_1 - ascii_i
                else:
                    is_borrowed = True
                    num = 11 - (ascii_i - ascii_0)
            elif ascii_0 == ascii_i:
                num = ascii_0 - ascii_i
                is_borrowed = False
            else:
                num = 10 - (ascii_i - ascii_0)
            res[i] = str(num)
        print(''.join(res))
    else:
        for i in range(n - 1, -1, -1):
            res[i] = str(ascii_9 - ord(s[i]))
        print(''.join(res))
for _ in range(int(input())):
    solve()

Solution (Python):
def solve_b(s):
    if s[0] != '9':
        ll = ''
        for i in s:
            x = int(i)
            y = 9 - x
            ll += str(y)
        return ll
    x = 11
    ll = ''
    resi = 0
    for i in s[::-1]:
        y = int(i) + resi
        z = x - y
        if z == 10:
            ll += '0'
            resi = 0
        elif z == 11:
            ll += '1'
            resi = 0
        else:
            ll += str(z)
            resi = 1
    return ll[::-1]
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = solve_b(s)
    print(ans)

Solution (Python):
def palindromic(n):
    ans = []
    if '9' not in n:
        for i in n:
            ans.append(str(9 - int(i)))
    else:
        if int(n[:2]) >= 12:
            other_thing = [1] * (len(n) + 1)
        else:
            other_thing = [9] * len(n)
        n = list(n)
        n.reverse()
        for ind in range(len(n)):
            if other_thing[ind] - int(n[ind]) < 0:
                other_thing[ind] += 10
                other_thing[ind + 1] -= 1
            ans.append(str(other_thing[ind] - int(n[ind])))
        ans.reverse()
    print(''.join(ans))
testcases = range(int(input()))
for case in testcases:
    input()
    palindromic(input())