Count numbers from a given range that can be expressed as sum of digits raised to the power of count of digits | Java program for the above approach ; Function to check if a number N can be expressed as sum of its digits raised to the power of the count of digits ; Stores the number of digits ; Stores the resultant number ; Return true if both the numbers are same ; Function to precompute and store for all numbers whether they can be expressed ; Mark all the index which are plus perfect number ; If true , then update the value at this index ; Compute prefix sum of the array ; Function to count array elements that can be expressed as the sum of digits raised to the power of count of digits ; Precompute the results ; Traverse the queries ; Print the resultant count ; Driver Code ; Function call
import java . util . * ; import java . io . * ; class GFG { static int R = 100005 ; static int [ ] arr = new int [ R ] ; public static boolean canExpress ( int N ) { int temp = N ; int n = 0 ; while ( N != 0 ) { N /= 10 ; n ++ ; } N = temp ; int sum = 0 ; while ( N != 0 ) { sum += ( ( int ) Math . pow ( N % 10 , n ) ) ; N /= 10 ; } if ( sum == temp ) return true ; return false ; } public static void precompute ( ) { for ( int i = 1 ; i < R ; i ++ ) { if ( canExpress ( i ) ) { arr [ i ] = 1 ; } } for ( int i = 1 ; i < R ; i ++ ) { arr [ i ] += arr [ i - 1 ] ; } } public static void countNumbers ( int [ ] [ ] queries , int N ) { precompute ( ) ; for ( int i = 0 ; i < N ; i ++ ) { int L1 = queries [ i ] [ 0 ] ; int R1 = queries [ i ] [ 1 ] ; System . out . print ( ( arr [ R1 ] - arr [ L1 - 1 ] ) + " ▁ " ) ; } } public static void main ( String args [ ] ) { int [ ] [ ] queries = { { 1 , 400 } , { 1 , 9 } } ; int N = queries . length ; countNumbers ( queries , N ) ; } }