Minimum number of palindromes required to express N as a sum | Set 1 | Declaring the DP table as global variable ; 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 elements in a sorted array A [ i . . j ] such that their sum is N ; Function to find the minimum number of palindromes that N can be expressed as a sum of ; Getting the list of all palindromes upto N ; Sorting the list of palindromes ; Returning the required value ; Driver code
dp = [ [ 0 for i in range ( 1000 ) ] for i in range ( 1000 ) ] NEW_LINE def createPalindrome ( input , isOdd ) : NEW_LINE INDENT n = input NEW_LINE 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 number = 0 NEW_LINE for j in range ( 2 ) : NEW_LINE INDENT i = 1 NEW_LINE number = createPalindrome ( i , j ) NEW_LINE while number <= N : NEW_LINE INDENT number = createPalindrome ( i , j ) NEW_LINE palindromes . append ( number ) NEW_LINE i += 1 NEW_LINE DEDENT DEDENT return palindromes NEW_LINE DEDENT def minimumSubsetSize ( A , i , j , N ) : NEW_LINE INDENT if ( not N ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i > j or A [ i ] > N ) : NEW_LINE INDENT return 10 ** 9 NEW_LINE DEDENT if ( dp [ i ] [ N ] ) : NEW_LINE INDENT return dp [ i ] [ N ] NEW_LINE DEDENT dp [ i ] [ N ] = min ( 1 + minimumSubsetSize ( A , i + 1 , j , N - A [ i ] ) , minimumSubsetSize ( A , i + 1 , j , N ) ) NEW_LINE return dp [ i ] [ N ] NEW_LINE DEDENT def minimumNoOfPalindromes ( N ) : NEW_LINE INDENT palindromes = generatePalindromes ( N ) NEW_LINE palindromes = sorted ( palindromes ) NEW_LINE return minimumSubsetSize ( palindromes , 0 , len ( palindromes ) - 1 , N ) NEW_LINE DEDENT N = 65 NEW_LINE print ( minimumNoOfPalindromes ( N ) ) NEW_LINE