import java.math.BigInteger;
import java.util.ArrayList;

class Day16
{
    public static ArrayList<String> getPermutations( String s )
    {
        ArrayList<String> results = new ArrayList<String>( );
        
        if( s.length( ) == 1 )
            results.add( s );
        else
            for( int i = 0; i < s.length( ); i++ )
            {
                char thisChar = s.charAt( i );
                String restOfString = s.substring( 0, i ) + s.substring( i + 1 );

                ArrayList<String> subPerms = getPermutations( restOfString );
                for( String str : subPerms )
                    results.add( thisChar + str );
            }
        
        return results;
    }
    
    /**
    public static boolean isPalindrome( String s )
    {
        if( s.length( ) <= 1 )
            return true;
        
        if( s.charAt( 0 ) != s.charAt( s.length( ) - 1 ) )
            return false;
        
        return isPalindrome( s.substring( 1, s.length( ) - 1 ) );
    }
     **/
    
    // low is first position in the string
    // high is last position in the string
    private static boolean isPalindrome( String s, int low, int high )
    {
        if( low >= high )   // length is essentially 1 or 0
            return true;
        
        if( s.charAt( low ) != s.charAt( high ) )
            return false;
        
        return isPalindrome( s, low + 1, high - 1 );
    }
    
    public static boolean isPalindrome( String s )
    {
        return isPalindrome( s, 0, s.length( ) - 1 );
    }
    
    public static BigInteger gcd( BigInteger m, BigInteger n )
    {
        if( m.compareTo( n ) < 0 )
            return gcd( n, m );
        
        // m > n
        if( n.compareTo( BigInteger.ZERO ) == 0 )
            return m;
        
        return gcd( n, m.mod( n ) );
    }
    
    public static BigInteger pow( BigInteger x, int n )
    {
        if( n == 0 )
            return BigInteger.ONE;
        
        if( n % 2 == 0 )
            return pow( x.multiply( x ), n / 2 );
        else
            return x.multiply( pow( x, n - 1 ) );
    }
    
    public static void main( String [ ] args )
    {
        BigInteger n = new BigInteger( "123456789012345678901234567890" );
        BigInteger m = new BigInteger( "234567891234945729683274958890" );
        int exp = 566;
       
        System.out.println( "m = " + m );
        System.out.println( "n = " + n );
        System.out.println( "My      gcd(m,n) = " + gcd( m, n ) );
        System.out.println( "Library gcd(m,n) = " + m.gcd( n ) );
        System.out.println( "Library pow(m,exp) = " + m.pow( exp ) );
        System.out.println( "My      pow(m,exp) = " + pow( m, exp ) );
       
      
        System.out.println( "hannah " + isPalindrome( "hannah" ) );
        System.out.println( "hanna  " + isPalindrome( "hanna" ) );
        System.out.println( "abcba  " + isPalindrome( "abcba" ) );
       
        
        ArrayList<String> perms = getPermutations( "ABCD" );
        System.out.println( perms );
    }
}