Check if a number can be expressed as sum of two Perfect powers | C ++ program for the above approach ; Function that returns true if n can be written as a ^ m + b ^ n ; Taking isSum boolean array for check the sum exist or not ; To store perfect squares ; Initially all sums as false ; If sum exist then push that sum into perfect square vector ; Mark all perfect powers as false ; Traverse each perfectPowers ; Calculating Sum with perfect powers array ; Driver Code ; Given Number n ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isSumOfPower ( int n ) { bool isSum [ n + 1 ] ; vector < int > perfectPowers ; perfectPowers . push_back ( 1 ) ; for ( int i = 0 ; i < ( n + 1 ) ; i ++ ) { isSum [ i ] = false ; } for ( long long int i = 2 ; i < ( n + 1 ) ; i ++ ) { if ( isSum [ i ] == true ) { perfectPowers . push_back ( i ) ; continue ; } for ( long long int j = i * i ; j > 0 && j < ( n + 1 ) ; j *= i ) { isSum [ j ] = true ; } } for ( int i = 0 ; i < perfectPowers . size ( ) ; i ++ ) { isSum [ perfectPowers [ i ] ] = false ; } for ( int i = 0 ; i < perfectPowers . size ( ) ; i ++ ) { for ( int j = i ; j < perfectPowers . size ( ) ; j ++ ) { int sum = perfectPowers [ i ] + perfectPowers [ j ] ; if ( sum < ( n + 1 ) ) isSum [ sum ] = true ; } } return isSum [ n ] ; } int main ( ) { int n = 9 ; if ( isSumOfPower ( n ) ) { cout << " true STRNEWLINE " ; } else { cout << " false STRNEWLINE " ; } }