Find the value of XXXX ... . . ( N times ) % M where N is large | Java implementation of the approach ; Iterative function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is >= p ; If y is odd , multiply x with result ; y must be even now y = y / 2 ; Function to return XXX ... . . ( N times ) % M ; Return the mod by M of smaller numbers ; Creating a string of N X 's ; Converting the string to int and calculating the modulo ; Checking the parity of N ; Dividing the number into equal half ; Utilizing the formula for even N ; Dividing the number into equal half ; Utilizing the formula for odd N ; Driver code ; Print XXX ... ( N times ) % M
class GFG { static int power ( int x , int y , int p ) { int res = 1 ; x = x % p ; while ( y > 0 ) { if ( y % 2 == 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } static int findModuloByM ( int X , int N , int M ) { if ( N < 6 ) { String temp = " " ; for ( int i = 0 ; i < N ; i ++ ) temp = temp + ( char ) ( X + 48 ) ; int res = Integer . parseInt ( temp ) % M ; return res ; } if ( N % 2 == 0 ) { int half = findModuloByM ( X , N / 2 , M ) % M ; int res = ( half * power ( 10 , N / 2 , M ) + half ) % M ; return res ; } else { int half = findModuloByM ( X , N / 2 , M ) % M ; int res = ( half * power ( 10 , N / 2 + 1 , M ) + half * 10 + X ) % M ; return res ; } } public static void main ( String [ ] args ) { int X = 6 , N = 14 , M = 9 ; System . out . println ( findModuloByM ( X , N , M ) ) ; } }