Project Euler 4 with python : Largest Palindrome Product

987 views Asked by At

I'm new to python ( and programming ) And i'm stuck in the Project Euler 4. The problem says :

"A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers."

Here's what i've come to so far :

ProductOfThree = []
ProductOfThreeSTR = []
PalindromicNumber = []
#This first for loop displays all the results possible from the product of two 3 digit Number
for k in range(100, 1000):
    for j in range(k, 1000):
        Result = k * j
        ProductOfThree.append(Result)
#This second loop converts the list of number to a list of string
for i in ProductOfThree:
    a = str(i)
    ProductOfThreeSTR.append(a)
#The third loop compare the digit of each number of the list to find all the palindromic number of that list
for d in ProductOfThreeSTR:
    if len(d) == 6:
        if (d[0] == d[5]) and (d[1] == d[4]) and (d[2] == d[3]):
            PalindromicNumber.append(d)
    elif len(d) == 5:
        if (d[0] == d[4]) and (d[1] == d[3]):
            PalindromicNumber.append(d)
#And finally here the program display the largest number of the list, which contains only the palindromic numbers
Largest = PalindromicNumber[0]
for p in PalindromicNumber:
    if Largest <= p:
        Largest = p        
print(Largest)

The program displays the number 99999 . After re-reading the program, i've figured out that the if statement with the len(d) == 5 is useless cause we want to display the largest number and a number with 6 digit is always greater that a number with five digit. After removing this part of the program, I'm having the result that i'm supposed to have ( 906609 ). But I'm still wondering, even if we are trying to find the palindromic number with 5 digit, normally they should be ignored when we will display the largest number of the list, so why it is giving the 99999 result?

3

There are 3 answers

0
sandor On BEST ANSWER

The problem is that in your last loop, when you're looking for the largest value, you compare strings instead of integers. Do this and it will give you the result you expect:

Largest = int(PalindromicNumber[0])
for p in PalindromicNumber:
    if Largest <= int(p):
        Largest = int(p)   

According to python docs string comparison uses lexicographical ordering:

The comparison uses lexicographical ordering: first the first two items are compared, and if they differ this determines the outcome of the comparison; if they are equal, the next two items are compared, and so on, until either sequence is exhausted.

0
Emily On

I think that the easiest way to do this is create the palindrome list using strings but get the max using integers. This is what I came up with:

x = 100

pal = []

while x < 1000:

for i in range(100,1000):
    for j in range(100,1000):
        prod = str(i*j)
        if prod == prod[::-1]:
            pal.append(int(prod))
        x = x+1

print(max(pal))

0
Veena Gowda On
//This would be more precise 
def largestpalin(n):
    lowerbound=0
    upperbound=0
    for i in range(1,n+1):
       upperbound=upperbound*10
       upperbound=upperbound+9
    lowebound=int(1+lowerbound/10)
    maxproduct=0
    for i in range(upperbound,lowerbound-1,-1):
        for j in range(i,lowebound-1,-1):
            product=i*j
            if product<maxproduct:
                 break
            num=product
            reverse=0
            while(num!=0):
               rem=num%10
               reverse=reverse*10+rem
               num=num//10
          if product==reverse and product>maxproduct:
               maxproduct=reverse
   return maxproduct
n=3
res=largestpalin(n)
print(res)