palindromic numbers in python

Question

Trying to find the largest palindrome that's the product of two three-digit numbers. Before I look up the infinitely more efficient and - more importantly - working solution, could you tell me what's wrong with my code? I just keep getting the empty set.

def palindrome():
    n = 100
    m = 100
    palind = []
    while n<=999:
        while m<=999:
            prod = n * m
            if str(prod) == str(prod)[::-1] and prod > palind[0]:
                palind.pop(0)
                palind.append(prod)
            return palind
            m = m + 1
        n = n + 1
        return palind

print palindrome()

Answer 1

You have 3 problems.

Problem 1: Returning early.

while n<=999:
    while m<=999:
        prod = n * m
        if str(prod) == str(prod)[::-1] and prod > palind[0]:
            palind.pop(0)
            palind.append(prod)
        # Here
        return palind
        m = m + 1
    n = n + 1
    # And here
    return palind

A return statement means the function is over now. It stops where it is, the caller gets the return value, and the caller goes on its way. You don't want to do that until the function is completely done with its work. Let's move the return to after the loops, when the function is done computing.

Problem 2: palind[0] is uninitialized.

while n<=999:
    while m<=999:
        prod = n * m
        #                                           Here  v
        if str(prod) == str(prod)[::-1] and prod > palind[0]:
            palind.pop(0)
            palind.append(prod)
        m = m + 1
    n = n + 1
return palind

Suppose your program is going along and it finds its first palindrome. It tries to compare it to palind[0], but there is no palind[0]! You need to take the first palindrome without trying to compare it to one that doesn't exist. Let's fix that.

Problem 3: Not resetting m.

palind = None
while n<=999:
    while m<=999:
        prod = n * m
        if str(prod) == str(prod)[::-1]:
            if palind is None or prod > palind:
                palind = prod
        m = m + 1
    n = n + 1
return palind

After the first iteration of the n loop, you need to go back through all possible m values with n=101. You don't do that; your code keeps m at 1000, so it doesn't go through the inner loop again. You could explicitly reset m, but it's much easier to use for loops instead of whiles. With all 3 problems fixed, your code looks like

palind = None
for n in xrange(100, 1000):
    for m in xrange(100, 1000):
        prod = n * m
        if str(prod) == str(prod)[::-1]:
            if palind is None or prod > palind:
                palind = prod
return palind

Answer 2

This shortcuts when it's impossible to return an i*j > the largest recorded and correctly returns 906609 (note, if you're in python 2, the below would work for you, but you'd prefer to use xrange instead of range to avoid creating unnecessary lists in memory):

def palindrome(floor=0, upto=999):
    '''
    return the largest palindrome product for all number from (but not including)
    floor to (and including) upto 
    '''
    start = upto
    largest = None
    for i in range(start, floor, -1): # decreasing from upto
        if i * upto < largest: # if True, impossible for higher product from combo
            break 
        for j in range(start, i-1, -1): # decrease from upto to not including i-1
            product = i*j
            if str(product) == str(product)[::-1]:
                if product > largest:
                    largest = product
    return largest

Usage:

>>> palindrome(99,999)
906609
>>> palindrome(10,13)
121
>>> palindrome(0,10)
9

The short-cutting is important because if given a very large number, it can take quite a while to return:

>>> palindrome(upto=100000000)
9999000000009999L

I also created a generator that hits every single combination from 0 to 999, and it returns 906609.

def palindrome(upto=1000):
    return max(i*j for i in range(upto) for j in range(upto) 
                if str(i*j) == str(i*j)[::-1])

But when running this palindrome as in:

>>> palindrome(upto=100000000)

The complete search will search all 100000000^2, and take far too long.

I first had written it like this, with the idea that it would short-cut and avoid iterating over every possible combination, but this is incorrect, it returns 888888:

def palindrome():
    start = 999
    largest = 0
    for i in range(start, 0, -1): # decreasing from 999
        if i * 999 < largest:
            return largest
        for j in range(start, i, -1): # decreasing from 999 to i
            if str(i*j) == str(i*j)[::-1]:
                largest = i*j

It first multiplies 999 times 999, then 998 times 999, then

998*998
997*999
997*998
997*997
...

But the results aren't monotonically decreasing (that is, each result is not guaranteed to be smaller than the previous.)

Answer 3

1. You are not re-initializing m = 100, after every iteration of the outer while loop

2. You are returning early. Remove the return statement in the inner loop

3. The last return statement should NOT be inside the outer while loop.

4. You never initialized palind list (Thanks to @user2357112)

Suggestions:

1. Don't use a list to maintain the biggest number. A simple variable is enough.

2. You don't have to convert the number to string twice in the same expression. Store the stringified number in a variable.

3. Use range functions to loop through the numbers

If I were to write this program, I would have done it like this

from itertools import product
def palindrome():
    numbers, result = range(1000, 100, -1), -1
    for num1, num2 in product(numbers, repeat = 2):
        prod  = num1 * num2
        sprod = str(prod)
        if sprod == sprod[::-1] and prod > result:
            result = prod
    return result

print palindrome()   # 906609

Answer 4

This is may not answer the question, but if you looking for to get palindromic numbers between range you can do this

def getPalindrome(lower, upper):
  listPalind = []
  for n in range(lower, upper):
    if str(n) == str(n)[::-1]:
      listPalind.append(n)
  return listPalind

# Usage
print(getPalindrome(100, 300))

# Results
[101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292]

Answer 5

def is_palindromic(s):
    if s == s[::-1]:
        return True
    else:
        return False

palind = []
    for i in range(100, 1000):
        for j in range(100,1000):
            product = i * j
            if is_palindromic(str(product)):
                palind.append(product)
    return max(palind)

#result : 906609

Answer 6

def isPalindrome(self, x: int):
    temp = 0
    x1 = x
    while x > 0:
        y = x % 10
        temp = temp * 10 + y
        x = x//10

    if(temp == x1):
        return True
    else:
        return False