Count numbers from a given range that can be expressed as sum of digits raised to the power of count of digits | Python 3 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
R = 100005 NEW_LINE arr = [ 0 for i in range ( R ) ] NEW_LINE def canExpress ( N ) : NEW_LINE INDENT temp = N NEW_LINE n = 0 NEW_LINE while ( N != 0 ) : NEW_LINE INDENT N //= 10 NEW_LINE n += 1 NEW_LINE DEDENT N = temp NEW_LINE sum = 0 NEW_LINE while ( N != 0 ) : NEW_LINE INDENT sum += pow ( N % 10 , n ) NEW_LINE N //= 10 NEW_LINE DEDENT return ( sum == temp ) NEW_LINE DEDENT def precompute ( ) : NEW_LINE INDENT for i in range ( 1 , R , 1 ) : NEW_LINE INDENT if ( canExpress ( i ) ) : NEW_LINE INDENT arr [ i ] = 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , R , 1 ) : NEW_LINE INDENT arr [ i ] += arr [ i - 1 ] NEW_LINE DEDENT DEDENT def countNumbers ( queries , N ) : NEW_LINE INDENT precompute ( ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT L1 = queries [ i ] [ 0 ] NEW_LINE R1 = queries [ i ] [ 1 ] NEW_LINE print ( ( arr [ R1 ] - arr [ L1 - 1 ] ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT queries = [ [ 1 , 400 ] , [ 1 , 9 ] ] NEW_LINE N = len ( queries ) NEW_LINE countNumbers ( queries , N ) NEW_LINE DEDENT