Comprueba si un número se puede expresar como la suma de dos potencias perfectas

Dado un número positivo N , la tarea es verificar si el número dado N se puede expresar en la forma de a ^x + b ^y donde x e y > 1 y a y b > 0. Si N se puede expresar en la forma dada luego imprime verdadero ; de lo contrario, imprime falso .

Ejemplos:

Entrada:  N = 5
Salida: verdadero
Explicación:
5 se puede expresar como 2 ² +1 ² 

Entrada: N = 15
Salida: falso

Planteamiento: La idea es usar el concepto de potencias perfectas para determinar si la suma existe o no. A continuación se muestran los pasos:

1. Cree una array (digamos perfectPower[] ) para almacenar los números que son una potencia perfecta o no .
2. Ahora la array perfectPower[] almacena todos los elementos que son potencia perfecta, por lo tanto, generamos todas las sumas de pares posibles de todos los elementos en esta array.
3. Mantenga la marca de la suma calculada en el paso anterior en una array isSum[] , ya que se puede expresar en forma de a ^x + b ^y  .
4. Después de los pasos anteriores, si isSum[N] es verdadero, imprima verdadero ; de lo contrario, imprima falso .

A continuación se muestra la implementación del enfoque anterior:

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

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function that returns true if n
// can be written as a^m+b^n
static boolean isSumOfPower(int n)
{
     
    // Taking isSum boolean array
    // for check the sum exist or not
    boolean []isSum = new boolean[n + 1];
 
    // To store perfect squares
    Vector<Integer> perfectPowers = new Vector<Integer>();
 
    perfectPowers.add(1);
 
    for(int i = 0; i < (n + 1); i++)
    {
         
        // Initially all sums as false
        isSum[i] = false;
    }
 
    for(int i = 2; i < (n + 1); i++)
    {
        if (isSum[i] == true)
        {
             
            // If sum exist then push
            // that sum into perfect
            // square vector
            perfectPowers.add(i);
            continue;
        }
 
        for(int j = i * i;
                j > 0 && j < (n + 1);
                j *= i)
        {
            isSum[j] = true;
        }
    }
 
    // Mark all perfect powers as false
    for(int i = 0;
            i < perfectPowers.size();
            i++)
    {
        isSum[perfectPowers.get(i)] = false;
    }
 
    // Traverse each perfectPowers
    for(int i = 0;
            i < perfectPowers.size();
            i++)
    {
        for(int j = i;
                j < perfectPowers.size();
                j++)
        {
             
            // Calculating Sum with
            // perfect powers array
            int sum = perfectPowers.get(i) +
                      perfectPowers.get(j);
 
            if (sum < (n + 1))
                isSum[sum] = true;
        }
    }
    return isSum[n];
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given number n
    int n = 9;
 
    // Function call
    if (isSumOfPower(n))
    {
        System.out.print("true\n");
    }
    else
    {
        System.out.print("false\n");
    }
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program for the above approach
 
# Function that returns true if n
# can be written as a^m+b^n
def isSumOfPower(n):
     
    # Taking isSum boolean array
    # for check the sum exist or not
    isSum = [0] * (n + 1)
 
    # To store perfect squares
    perfectPowers = []
 
    perfectPowers.append(1)
 
    for i in range(n + 1):
 
        # Initially all sums as false
        isSum[i] = False
     
    for i in range(2, n + 1):
        if (isSum[i] == True):
 
            # If sum exist then push
            # that sum into perfect
            # square vector
            perfectPowers.append(i)
            continue
         
        j = i * i
        while(j > 0 and j < (n + 1)):
            isSum[j] = True
            j *= i
         
    # Mark all perfect powers as false
    for i in range(len(perfectPowers)):
        isSum[perfectPowers[i]] = False
     
    # Traverse each perfectPowers
    for i in range(len(perfectPowers)):
        for j in range(len(perfectPowers)):
 
            # Calculating Sum with
            # perfect powers array
            sum = (perfectPowers[i] +
                   perfectPowers[j])
 
            if (sum < (n + 1)):
                isSum[sum] = True
         
    return isSum[n]
 
# Driver Code
 
# Given Number n
n = 9
 
# Function call
if (isSumOfPower(n)):
    print("true")
else:
    print("false")
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that returns true if n
// can be written as a^m+b^n
static bool isSumOfPower(int n)
{
     
    // Taking isSum bool array
    // for check the sum exist or not
    bool []isSum = new bool[n + 1];
 
    // To store perfect squares
    List<int> perfectPowers = new List<int>();
 
    perfectPowers.Add(1);
 
    for(int i = 0; i < (n + 1); i++)
    {
         
        // Initially all sums as false
        isSum[i] = false;
    }
 
    for(int i = 2; i < (n + 1); i++)
    {
        if (isSum[i] == true)
        {
             
            // If sum exist then push
            // that sum into perfect
            // square vector
            perfectPowers.Add(i);
            continue;
        }
 
        for(int j = i * i;
                j > 0 && j < (n + 1);
                j *= i)
        {
            isSum[j] = true;
        }
    }
 
    // Mark all perfect powers as false
    for(int i = 0;
            i < perfectPowers.Count;
            i++)
    {
        isSum[perfectPowers[i]] = false;
    }
 
    // Traverse each perfectPowers
    for(int i = 0;
            i < perfectPowers.Count;
            i++)
    {
        for(int j = i;
                j < perfectPowers.Count;
                j++)
        {
             
            // Calculating Sum with
            // perfect powers array
            int sum = perfectPowers[i] +
                      perfectPowers[j];
 
            if (sum < (n + 1))
                isSum[sum] = true;
        }
    }
    return isSum[n];
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given number n
    int n = 9;
 
    // Function call
    if (isSumOfPower(n))
    {
        Console.Write("true\n");
    }
    else
    {
        Console.Write("false\n");
    }
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// JavaScript  program to implement
// the above approach
 
// Function that returns true if n
// can be written as a^m+b^n
function isSumOfPower(n)
{
       
    // Taking isSum boolean array
    // for check the sum exist or not
    let isSum = Array(n+1).fill(0);
   
    // To store perfect squares
    let perfectPowers = [];
   
    perfectPowers.push(1);
   
    for(let i = 0; i < (n + 1); i++)
    {
           
        // Initially all sums as false
        isSum[i] = false;
    }
   
    for(let i = 2; i < (n + 1); i++)
    {
        if (isSum[i] == true)
        {
               
            // If sum exist then push
            // that sum into perfect
            // square vector
            perfectPowers.push(i);
            continue;
        }
   
        for(let j = i * i;
                j > 0 && j < (n + 1);
                j *= i)
        {
            isSum[j] = true;
        }
    }
   
    // Mark all perfect powers as false
    for(let i = 0;
            i < perfectPowers.length;
            i++)
    {
        isSum[perfectPowers[i]] = false;
    }
   
    // Traverse each perfectPowers
    for(let i = 0;
            i < perfectPowers.length;
            i++)
    {
        for(let j = i;
                j < perfectPowers.length;
                j++)
        {
               
            // Calculating Sum with
            // perfect powers array
            let sum = perfectPowers[i] +
                      perfectPowers[j];
   
            if (sum < (n + 1))
                isSum[sum] = true;
        }
    }
    return isSum[n];
}
 
// Driver Code
 
    // Given number n
    let n = 9;
   
    // Function call
    if (isSumOfPower(n))
    {
        document.write("true\n");
    }
    else
    {
        document.write("false\n");
    }
 
</script>

true

Complejidad temporal: O(N)
Espacio auxiliar: O(N)