Smallest N digit number whose sum of square of digits is a Perfect Square | Java 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 string representing the N digit number ; Driver code ; Initialise N
class GFG { static int isSquare ( int n ) { int k = ( int ) Math . sqrt ( n ) ; return k * k == n ? 1 : 0 ; } static int calculate ( int pos , int prev , int sum , int [ ] v ) { if ( pos == v . length ) return isSquare ( sum ) ; for ( int i = prev ; i <= 9 ; i ++ ) { v [ pos ] = i ; sum += i * i ; if ( calculate ( pos + 1 , i , sum , v ) != 0 ) return 1 ; sum -= i * i ; } return 0 ; } static String minValue ( int n ) { int [ ] v = new int [ n ] ; if ( calculate ( 0 , 1 , 0 , v ) != 0 ) { String answer = " " ; for ( int i = 0 ; i < v . length ; i ++ ) answer += ( char ) ( v [ i ] + '0' ) ; return answer ; } else return " - 1" ; } public static void main ( String [ ] args ) { int N = 2 ; System . out . println ( minValue ( N ) ) ; } }