Check if N can be converted to the form K power K by the given operation | Java implementation to Check whether a given number N can be converted to the form K power K by the given operation ; Function to check if a number is converatable ; Check if n is of the form k ^ k ; Check if the subproblem has been solved before ; Iterate through each digit of n ; Check if it is possible to obtain number of given form ; Reduce the number each time ; Store and return the answer to this subproblem ; Function to check the above method ; Initialise the dp table ; Check if conversion if possible ; Driver code ; Pre store K power K form of numbers Loop till 8 , because 8 ^ 8 > 10 ^ 7
import java . util . * ; class GFG { static HashSet < Integer > kPowKform = new HashSet < > ( ) ; static int [ ] dp = new int [ 100005 ] ; static int func ( int n ) { if ( n <= 0 ) return 0 ; if ( kPowKform . contains ( n ) ) return 1 ; if ( dp [ n ] != - 1 ) return dp [ n ] ; int answer = 0 ; int x = n ; while ( x > 0 ) { int d = x % 10 ; if ( d != 0 ) { if ( func ( n - d * d ) != 0 ) { answer = 1 ; break ; } } x /= 10 ; } return dp [ n ] = answer ; } static void canBeConverted ( int n ) { for ( int i = 0 ; i < n ; i ++ ) dp [ i ] = - 1 ; if ( func ( n ) == 0 ) System . out . print ( " Yes " ) ; else System . out . print ( " No " ) ; } public static void main ( String [ ] args ) { int N = 13 ; for ( int i = 1 ; i <= 8 ; i ++ ) { int val = 1 ; for ( int j = 1 ; j <= i ; j ++ ) val *= i ; kPowKform . add ( val ) ; } canBeConverted ( N ) ; } }