Return to Blog entry

Python 2.5 solution Mike 3rd November, 2008 13:48 (UTC)
def odd(n, x=1): return odd(abs(n)) if n < 0 else n if n<2 else odd(n-x,1) if x+x>n else odd(n,x+x)
Python 2.5 solution Mike 30th November, 2008 17:53 (UTC)

As Alexey rightly points out, it is O((log n)^2)

Also, as Kirit notes, it can be better put as:

def odd(n, x=1): return odd(abs(n)) if n < 0 else n==1 if n<2 else odd(n-x) if x+x>n else odd(n,x+x)

This one is O(log(n)) I think. Doesn't win any points for prettiness though:

def odd (n, p=1):
    if n  < 0: return odd(abs(n))
    q = p+p
    a = odd(n, q) if q < n else q
    a = a-p if a > n else a+p
    return a == n if p == 1 else a

It basically does what Alexey's code does except the powers of two are stored directly on the stack. I'm sure someone can come up with a prettier way of doing the same thing.

see http://www.kirit.com/Thread:/1724915

Both of these functions use a test at the start to see if n is negative. We can factor that out into a decorator:

ignores_sign = lambda fn: lambda n, *args: fn(abs(n), *args)
@ignores_sign
def odd(n, x=1): return n==1 if n<2 else odd(n-x) if x+x>n else odd(n,x+x)
@ignores_sign
def odd_(n, p=1):
    q = p+p
    a = odd_(n, q) if q < n else q
    a = a-p if a > n else a+p
    return a == n if p == 1 else a

However, the best thing about all of these functions is that none of them use any arrays or indexing, or use any square brackets whatsoever. This is the crucial factor in each function's design if they are to be even remotely legible on Kirit's site.

kirit.com