Count of numbers in range [ L , R ] which can be represented as sum of two perfect powers | Java program for the above approach ; Function to find the number of numbers that can be expressed in the form of the sum of two perfect powers ; Stores all possible powers ; Push 1 and 0 in it ; Iterate over all the exponents ; Iterate over all possible numbers ; This loop will run for a maximum of sqrt ( R ) times ; Push this power in the array pows [ ] ; Increase the number ; Stores if i can be expressed as the sum of perfect power or not ; Iterate over all possible pairs of the array pows [ ] ; The number is valid ; Find the prefix sum of the array ok [ ] ; Return the count of required number ; Driver Code
import java . util . * ; class GFG { static int TotalPerfectPowerSum ( int L , int R ) { ArrayList < Integer > pows = new ArrayList < Integer > ( ) ; pows . add ( 0 ) ; pows . add ( 1 ) ; for ( int p = 2 ; p < 25 ; p ++ ) { int num = 2 ; while ( ( int ) ( Math . pow ( num , p ) + 0.5 ) <= R ) { pows . add ( ( int ) ( Math . pow ( num , p ) + 0.5 ) ) ; num ++ ; } } int [ ] ok = new int [ R + 2 ] ; for ( int i = 0 ; i < pows . size ( ) ; i ++ ) { for ( int j = 0 ; j < pows . size ( ) ; j ++ ) { if ( pows . get ( i ) + pows . get ( j ) <= R && pows . get ( i ) + pows . get ( j ) >= L ) { ok [ pows . get ( i ) + pows . get ( j ) ] = 1 ; } } } for ( int i = 1 ; i <= R ; i ++ ) { ok [ i ] += ok [ i - 1 ] ; } return ok [ R ] - ok [ L - 1 ] ; } public static void main ( String args [ ] ) { int L = 5 , R = 8 ; System . out . print ( TotalPerfectPowerSum ( L , R ) ) ; } }