Sum of all N | Java program for the above approach ; Function to find a ^ b efficiently ; Base Case ; To store the value of a ^ b ; Multiply temp by a until b is not 0 ; Return the final ans a ^ b ; Function to find sum of all N - digit palindromic number divisible by 9 ; Base Case ; If N is even , decrease ways by 1 ; Find the total number of ways ; Iterate over [ 1 , N ] and find the sum at each index ; Print the final Sum ; Driver Code
class GFG { static int MOD = 1000000007 ; static int power ( int a , int b ) { if ( b == 0 ) return 1 ; int temp = power ( a , b / 2 ) ; temp = ( temp * temp ) % MOD ; if ( b % 2 != 0 ) { temp = ( temp * a ) % MOD ; } return temp ; } static void palindromicSum ( int N ) { int sum = 0 , res , ways ; if ( N == 1 ) { System . out . print ( "9" + "NEW_LINE"); return ; } if ( N == 2 ) { System . out . print ( "99" + "NEW_LINE"); return ; } ways = N / 2 ; if ( N % 2 == 0 ) ways -- ; res = power ( 9 , ways - 1 ) ; for ( int i = 0 ; i < N ; i ++ ) { sum = sum * 10 + 45 * res ; sum %= MOD ; } System . out . print ( sum + "NEW_LINE"); } public static void main ( String [ ] args ) { int N = 3 ; palindromicSum ( N ) ; } }