Dec 2013
1 / 5
Dec 2013
Dec 2013
suryak
Dec '13

def dig(l, n, pos):
    """pos: 1 to n; left to right"""
    pos = l - pos + 1
    k = 10 ** pos
    r = n % k
    return r / (k / 10)
def inc_dig(l, n, val, pos):
    """pos: 1 to n; left to right"""
    pos = l - pos + 1
    if pos == 1:
        return n + 1
    return n + (val * (10 ** (pos-1)))
def replace_dig(l, n, posi, posj):
    """pos: 1 to n; left to right"""
    d1 = dig(l, n, posi)
    d2 = dig(l, n, posj)
    sub = (d2 - d1) * (10 ** (l - posj))
    n -= sub
    return n
def palin(n):
    l = len(str(n))
    if l % 2 == 0:
        k = l / 2
    else:
        k = (l - 1) / 2
    i = 1
    while i <= k:
        if str(n) == str(n)[::-1]:
            return n
        if dig(l, n, i) < dig(l, n, l-i+1):
            n = inc_dig(l, n, 1, l-i)
        n = replace_dig(l, n, i, l-i+1)
        if dig(l, n, l-i) == 0:
            i -= 1
            continue
        i += 1
    return n
t = int(raw_input())
for i in range(t):
    print palin(int(raw_input()) + 1)

I am new to algos and spoj and above is my code.
I actually tried to operate on strings first.. My code was successful but exceeded the time limit. This time, I thought to play with numbers directly..
This code is unfortunately raising NZEC.. strange..
Can anyone help me find why exactly its raising.

Thanks

suryak
Dec '13

I have made little bit of changes and now I am not getting NZEC but time is exceeding.
This is going crazy.. can anyone please help me where its consuming time?
my code would be running at O(n) but still !! angry 

import math
def dig(l, n, pos):
    """pos: 1 to n; left to right"""
    pos = l - pos + 1
    k = 10 ** pos
    r = n % k
    return r / (k / 10)
def inc_dig(l, n, val, pos):
    """pos: 1 to n; left to right"""
    pos = l - pos + 1
    if pos == 1:
        return n + 1
    return n + (val * (10 ** (pos-1)))
def replace_dig(l, n, posi, posj):
    """pos: 1 to n; left to right"""
    d1 = dig(l, n, posi)
    d2 = dig(l, n, posj)
    sub = (d2 - d1) * (10 ** (l - posj))
    n -= sub
    return n
def palin(n):
    l = int(math.log10(n)) + 1
    if l % 2 == 0:
        k = l / 2
    else:
        k = (l - 1) / 2
    i = 1
    while i <= k:
        d_i = dig(l, n, i)
        d_n = dig(l, n, l-i+1)
        if d_i != d_n:
            if d_i < d_n:
                n = inc_dig(l, n, 1, l-i)
            n = replace_dig(l, n, i, l-i+1)
        i += 1
    return n
t = input()
for i in range(t):
    print palin(input() + 1)
numerix
Dec '13

You didn't do some testing with large random data, did you?
That's what you should do. You will certainly find out by yourself where the (narrowest) bottleneck is.

suryak
Dec '13

Well, is there a way I can find some large data to try?

numerix
Dec '13

You have to generate the data on your own:
Some small random inputs, some large random inputs and some handmade "corner cases", if there are any.