Check if a number can be formed by sum of a number and its reverse

Question

I want to check if a given number can be formed by another number say b and reverse(b). For example 12 == 6+6, 22 == 11 + 11 and 121 == 29+92. One thing I have figured out is if the number is multiple of 11 or it is an even number less than 20, then it can be formed. I tried to implement this below:

num = 121
if num%11==0:
    print('Yes')
else:
    if num%2==0 and num<20:
        print('Yes')
    else:
        for j in range(11,(int(num)//2)+1):
            if j+int(str(j)[::-1])==num:
                print('Yes')
                break
         

However, if the condition goes into the for loop, it gives TLE. Can any other conditions be given?

Update: If the reversed number has trailing zeroes, it should be removed and then added. For example: 101 == 100+1. I am looking for an optimized form of my code. Or I think I am missing some conditions which can take O(1) time, similar to the condition if num%11==0: print('Yes')

Answer 1

All the previous answers are not really a check. It's more a brute force try and error. So let's do it a little bit smarter.

We start with a number, for example 246808642. we can reduce the problem to the outer 2 place values at the end and start of the number. Let us call this values A and B at the front and Y and Z on the back. the rest, in the middle, is Π. So our number looks now ABΠYZ with A = 2, B = 4, Π = 68086, Y = 4 and Z = 2. (one possible pair of numbers to sum up for this is 123404321). Is A equal to 1, this is only possible for a sum greater 10 (An assumption, but i guess it works, some proof would be nice!).

so if it is a one, we know that the second last number is one greater by the carry over. So we ignore A for the moment and compare B to Z, because they should be the same because both are the result of the addition of the same two numbers. if so, we take the remaining part Π and reduce Y by one (the carry over from the outer addition), and can start again at the top of this chart with Π(Y-1). Only a carry over can make B one bigger than Z, if it's so, we can replace B by one and start with 1Π(Y-1) at the top. B-1!=Z and B!=Z, we can stop, this isnt possible for such a number which is the sum of a number and its reversed.

If A != 1, we do everything similiar as before but now we use A instead of B. (I cut this here. The answer is long enough.)

The code:

import time
def timing(f):
    def wrap(*args, **kwargs):
        time1 = time.time()
        ret = f(*args, **kwargs)
        time2 = time.time()
        print('{:s} function took {:.3f} ms'.format(f.__name__, (time2-time1)*1000.0))

        return ret
    return wrap

@timing
def check(num):
    num = str(num)
    if (int(num) < 20 and int(num)%2 == 0) or (len(num) ==2 and int(num)%11 == 0):
        return print('yes')
    if len(num) <= 2 and int(num)%2 != 0:
        return print('no')
    # get the important place values of the number x
    A = num[0]
    B = num[1]
    remaining = num[2:-2]
    Y = num[-2]
    Z = num[-1]
    # check if A = 1
    if A == '1':
        # A = 1
        # check if B == Z
        if B == Z:
            # so the outest addition matches perfectly and no carry over from inner place values is involved
            # reduce the last digit about one and check again.
            check(remaining + (str(int(Y)-1) if Y != '0' else '9'))
        elif int(B)-1 == int(Z):
            # so the outest addition matches needs a carry over from inner place values to match, so we add to
            # to the remaining part of the number a leading one
            # we modify the last digit of the remaining place values, because the outest had a carry over
            check('1' + remaining + (str(int(Y)-1) if Y != '0' else '9'))
        else:
            print("Not able to formed by a sum of a number and its reversed.")
    else:
        # A != 1
        # check if A == Z
        if A == Z:
            # so the outest addition matches perfectly and no carry over from inner place values is involved
            check(B + remaining + Y)
        elif int(A) - 1 == int(Z):
            # so the outest addition matches needs a carry over from inner place values to match, so we add to
            # to the remaining part of the number a leading one
            # we modify the last digit of the remaining place values, because the outest had a carry over
            check('1' + B + remaining + Y)
        else:
            print("Not able to formed by a sum of a number and its reversed.")

@timing
def loop_check(x):
    for i in range(x + 1):
        if i == int(str(x - i)[::-1]) and not str(x - i).endswith("0"):
            print('yes, by brute force')
            break

loop_check(246808642)
check(246808642)

Result:

yes, by brute force
loop_check function took 29209.069 ms
Yes
check function took 0.000 ms

And another time we see the power of math. Hope this work for you!