Pandigital products : Problem 32 : Project Euler : Python Code

Pandigital products : Problem 32 : Project Euler

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

 

 

First note that if m X n = P, by concatenating m,n and P it will be a 9-digit pandigital number if both in m & n none of the digits are repeated. I have use the function checkOneDigit(numb) to check whether in m or n frequncy of any digit is greater than 1. checkPandigital(numb) simply checks whether a number is n-digit pandigital or not. Next task is to determine the upper limit of m and n. Observe that if m or n is a 5-digit number, after concatenation it will never form a 9-digit pandigital number. Since P will be of atleast 5-digits. So after concatenation the number will consist of 11 digits (even if m is of 1 digit number) Ex. 12345 X m = abcde, after concatenation it results in 12345mabcde, (at-least 11 digits) by Pigeon Hole Principle at least on of the digits 1,2,3,....,9 has to be repeated. Hence Max(m,n) <= 4999, within this range m and n are filtered using checkOneDigit(numb)

Python Code 

  

def pandigitalProducts():

    def checkPandigital(numb):
        flag = True
        strNumber = str(numb)
        length = len(strNumber)
        if '0' in strNumber:
            return False
        nList = [0 for i in range (length)]
        for i in range (length):
            nList[i] = int(strNumber[i])
            if int(strNumber[i]) > length:
                flag = False
        if 0  in nList:
            return False       
        if flag == False:
            return False
        else:
            for i in range (length):
                if nList.count(int(strNumber[i])) > 1 :
                    flag = False
                    break
            return flag
          
    def checkOneDigit(numb):
        flag = True
        strNumber = str(numb)
        length = len(strNumber)
        if '0' in strNumber:
            return False
        nList = [0 for i in range (length)]
        for i in range (length):
            nList[i] = int(strNumber[i])
        for i in range (length):
            if nList.count(int(strNumber[i])) > 1 :
                    flag = False
                    break
        return flag
              
    sumPandigital = 0
    upperLimit = 9999
    n = 1
    pandigitalList = ()
    """ pandigitalList contains the all possible values of m and n """
    while n <= upperLimit:
        if checkOneDigit(n) == True:
            pandigitalList = pandigitalList + (n,)
        n = n+1  
    """print pandigitalList    """
    panProduct = ()
    sumP = 0  
    for d in pandigitalList:
        m = d
        for x in pandigitalList:
            product = 1
            n = x
            product = m*n
            strNumb = ""
            strNumb = strNumb + (str(m)+str(n)+str(product))
            if len(strNumb) == 9:
                if checkPandigital(int(strNumb)) == True:
                    if product not in panProduct:
                        panProduct = panProduct + (product,)
                        sumP = sumP + product
                        print m,"X",n,"=",product,"Partial Sum--------------",sumP  
    print "Required Sum is:",sumP  
pandigitalProducts()