Minimum number of palindromes required to express N as a sum | Set 2 | A utility for creating palindrome ; checks if number of digits is odd or even if odd then neglect the last digit of _input in finding reverse as in case of odd number of digits middle element occur once ; Creates palindrome by just appending reverse of number to itself ; Function to generate palindromes ; Run two times for odd and even length palindromes ; Creates palindrome numbers with first half as i . Value of j decides whether we need an odd length or even length palindrome . ; Function to find the minimum number of palindromes required to express N as a sum ; Checking if the number is a palindrome ; Getting the list of all palindromes upto N ; Sorting the list of palindromes ; The answer is three if the control reaches till this point ; Driver code
def createPalindrome ( _input , isOdd ) : NEW_LINE INDENT n = palin = _input NEW_LINE if isOdd : NEW_LINE INDENT n //= 10 NEW_LINE DEDENT while n > 0 : NEW_LINE INDENT palin = palin * 10 + ( n % 10 ) NEW_LINE n //= 10 NEW_LINE DEDENT return palin NEW_LINE DEDENT def generatePalindromes ( N ) : NEW_LINE INDENT palindromes = [ ] NEW_LINE for j in range ( 0 , 2 ) : NEW_LINE INDENT i = 1 NEW_LINE number = createPalindrome ( i , j ) NEW_LINE while number <= N : NEW_LINE INDENT palindromes . append ( number ) NEW_LINE i += 1 NEW_LINE number = createPalindrome ( i , j ) NEW_LINE DEDENT DEDENT return palindromes NEW_LINE DEDENT def minimumNoOfPalindromes ( N ) : NEW_LINE INDENT b = a = str ( N ) NEW_LINE b = b [ : : - 1 ] NEW_LINE if a == b : NEW_LINE INDENT return 1 NEW_LINE DEDENT palindromes = generatePalindromes ( N ) NEW_LINE palindromes . sort ( ) NEW_LINE l , r = 0 , len ( palindromes ) - 1 NEW_LINE while l < r : NEW_LINE INDENT if palindromes [ l ] + palindromes [ r ] == N : NEW_LINE INDENT return 2 NEW_LINE DEDENT elif palindromes [ l ] + palindromes [ r ] < N : NEW_LINE INDENT l += 1 NEW_LINE DEDENT else : NEW_LINE INDENT r -= 1 NEW_LINE DEDENT DEDENT return 3 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 65 NEW_LINE print ( minimumNoOfPalindromes ( N ) ) NEW_LINE DEDENT