Smallest N digit number whose sum of square of digits is a Perfect Square | Python3 implementation to find Smallest N digit number whose sum of square of digits is a Perfect Square ; function to check if number is a perfect square ; function to calculate the smallest N digit number ; place digits greater than equal to prev ; check if placing this digit leads to a solution then return it ; else backtrack ; create a representing the N digit number ; Driver code ; initialise N
from math import sqrt NEW_LINE def isSquare ( n ) : NEW_LINE INDENT k = int ( sqrt ( n ) ) NEW_LINE return ( k * k == n ) NEW_LINE DEDENT def calculate ( pos , prev , sum , v ) : NEW_LINE INDENT if ( pos == len ( v ) ) : NEW_LINE INDENT return isSquare ( sum ) NEW_LINE DEDENT for i in range ( prev , 9 + 1 ) : NEW_LINE INDENT v [ pos ] = i NEW_LINE sum += i * i NEW_LINE if ( calculate ( pos + 1 , i , sum , v ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT sum -= i * i NEW_LINE DEDENT return 0 NEW_LINE DEDENT def minValue ( n ) : NEW_LINE INDENT v = [ 0 ] * ( n ) NEW_LINE if ( calculate ( 0 , 1 , 0 , v ) ) : NEW_LINE INDENT answer = " " NEW_LINE for i in range ( len ( v ) ) : NEW_LINE INDENT answer += chr ( v [ i ] + ord ( '0' ) ) NEW_LINE DEDENT return answer NEW_LINE DEDENT else : NEW_LINE INDENT return " - 1" NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE print ( minValue ( N ) ) NEW_LINE DEDENT