Comprobar si un número se puede representar como la suma de dos cubos perfectos positivos

Dado un número entero N , la tarea es verificar si N puede representarse como la suma de dos cubos perfectos positivos o no.

Ejemplos:

Entrada: N = 28
Salida: Sí
Explicación: 
Dado que, 28 = 27 + 1 = 3 ³ + 1 ³ .
Por lo tanto, la respuesta requerida es Sí.

Entrada: N = 34
Salida: No

Enfoque: La idea es almacenar los cubos perfectos de todos los números desde 1 hasta la raíz cúbica de N en un Mapa y comprobar si N se puede representar como la suma de dos números presentes en el Mapa o no . Siga los pasos a continuación para resolver el problema:

• Inicialice un mapa ordenado , digamos cubos, para almacenar los cubos perfectos de los primeros N números naturales en orden ordenado.
• Recorra el mapa y verifique que el par tenga una suma igual a N .
• Si se encuentra que dicho par tiene una suma N , imprima «Sí» . De lo contrario, escriba “No” .

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 to check if N can be represented
// as sum of two perfect cubes or not
void sumOfTwoPerfectCubes(int N)
{
    // Stores the perfect cubes
    // of first N natural numbers
    map<int, int> cubes;
    for (int i = 1; i * i * i <= N; i++)
        cubes[i * i * i] = i;
 
    // Traverse the map
    map<int, int>::iterator itr;
    for (itr = cubes.begin();
         itr != cubes.end(); itr++) {
 
        // Stores first number
        int firstNumber = itr->first;
 
        // Stores second number
        int secondNumber = N - itr->first;
 
        // Search the pair for the first
        // number to obtain sum N from the Map
        if (cubes.find(secondNumber)
            != cubes.end()) {
            cout << "True";
            return;
        }
    }
 
    // If N cannot be represented as
    // sum of two positive perfect cubes
    cout << "False";
}
 
// Driver Code
int main()
{
    int N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    sumOfTwoPerfectCubes(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to check if N can be represented
  // as sum of two perfect cubes or not
  public static void sumOfTwoPerfectCubes(int N)
  {
 
    // Stores the perfect cubes
    // of first N natural numbers
    HashMap<Integer, Integer> cubes = new HashMap<>();
    for (int i = 1; i * i * i <= N; i++)
      cubes.put((i * i * i), i);
 
    // Traverse the map
    Iterator<Map.Entry<Integer, Integer> > itr
      = cubes.entrySet().iterator();
    while (itr.hasNext())
    {
      Map.Entry<Integer, Integer> entry = itr.next();
 
      // Stores first number
      int firstNumber = entry.getKey();
 
      // Stores second number
      int secondNumber = N - entry.getKey();
 
      // Search the pair for the first
      // number to obtain sum N from the Map
      if (cubes.containsKey(secondNumber))
      {
        System.out.println("True");
        return;
      }
    }
 
    // If N cannot be represented as
    // sum of two positive perfect cubes
    System.out.println("False");
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    sumOfTwoPerfectCubes(N);
  }
}
 
// This code is contributed by shailjapriya.

# Python3 program for the above approach
 
# Function to check if N can be represented
# as sum of two perfect cubes or not
def sumOfTwoPerfectCubes(N) :
 
    # Stores the perfect cubes
    # of first N natural numbers
    cubes = {}
    i = 1
    while i*i*i <= N :
        cubes[i*i*i] = i
        i += 1
  
    # Traverse the map
    for itr in cubes :
  
        # Stores first number
        firstNumber = itr
  
        # Stores second number
        secondNumber = N - itr
  
        # Search the pair for the first
        # number to obtain sum N from the Map
        if secondNumber in cubes :
            print("True", end = "")
            return
  
    # If N cannot be represented as
    # sum of two positive perfect cubes
    print("False", end = "")
 
N = 28
 
# Function call to check if N
# can be represented as
# sum of two perfect cubes or not
sumOfTwoPerfectCubes(N)
 
# This code is contributed by divyeshrabadiya07.

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG{
 
  // Function to check if N can be represented
  // as sum of two perfect cubes or not
  public static void sumOfTwoPerfectCubes(int N)
  {
 
    // Stores the perfect cubes
    // of first N natural numbers
    Dictionary<int,
             int> cubes = new Dictionary<int,
                                      int>();
    for (int i = 1; i * i * i <= N; i++)
      cubes.Add((i * i * i), i);
     
    var val = cubes.Keys.ToList();
    foreach(var key in val)
    {
      // Stores first number
      int firstNumber = cubes[1];
 
      // Stores second number
      int secondNumber = N - cubes[1];
 
      // Search the pair for the first
      // number to obtain sum N from the Map
      if (cubes.ContainsKey(secondNumber))
      {
        Console.Write("True");
        return;
      }
    }
 
    // If N cannot be represented as
    // sum of two positive perfect cubes
    Console.Write("False");
  }
 
 
// Driver Code
static public void Main()
{
    int N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    sumOfTwoPerfectCubes(N);
}
}
 
// This code is contributed by code_hunt.

<script>
 
// Javascript program for the above approach
 
// Function to check if N can be represented
// as sum of two perfect cubes or not
function sumOfTwoPerfectCubes(N)
{
    // Stores the perfect cubes
    // of first N natural numbers
    var cubes = new Map();
    for (var i = 1; i * i * i <= N; i++)
        cubes.set(i * i * i, i);
 
    var ans = false;
    // Traverse the map
    cubes.forEach((value, key) => {
        // Stores first number
        var firstNumber = key;
 
        // Stores second number
        var secondNumber = N - value;
 
        // Search the pair for the first
        // number to obtain sum N from the Map
        if (cubes.has(secondNumber)) {
            document.write( "True");
            ans = true;
            return;
        }
    });
   
    if(ans)
    {
        return;
    }
    // If N cannot be represented as
    // sum of two positive perfect cubes
    document.write( "False");
}
 
// Driver Code
var N = 28;
// Function call to check if N
// can be represented as
// sum of two perfect cubes or not
sumOfTwoPerfectCubes(N);
 
 
</script>

True

Complejidad de tiempo: O(N ^1/3 * log(N ^1/3 ))  
Espacio auxiliar: O(N ^1/3 ) 

Enfoque 2:

Usando dos punteros:

Declararemos lo a 1 y hola a la raíz cúbica de n (el número dado), luego por (lo<=hi) esta condición, si la corriente es menor que n incrementaremos lo y por otro lado si es mayor entonces disminuir el hi, donde la corriente es (lo*lo*lo + hi*hi*hi)

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if N can be represented
// as sum of two perfect cubes or not
bool sumOfTwoCubes(int n)
{
    long long int lo = 1, hi = (long long int)cbrt(n);
    while (lo <= hi) {
        long long int curr = (lo * lo * lo + hi * hi * hi);
        if (curr == n)
            // if it is same return true;
            return true;
        if (curr < n)
            // if the curr smaller than n increment the lo
            lo++;
        else
            // if the curr is greater than curr decrement
            // the hi
            hi--;
    }
    return false;
}
 
// Driver Code
int main()
{
    int N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    if (sumOfTwoCubes(N)) {
        cout << "True";
    }
    else {
        cout << "False";
    }
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG
{
 
// Function to check if N can be represented
// as sum of two perfect cubes or not
static boolean sumOfTwoCubes(int n)
{
    int lo = 1, hi = (int)Math.cbrt(n);
    while (lo <= hi) {
        int curr = (lo * lo * lo + hi * hi * hi);
        if (curr == n)
           
            // if it is same return true;
            return true;
        if (curr < n)
           
            // if the curr smaller than n increment the lo
            lo++;
        else
           
            // if the curr is greater than curr decrement
            // the hi
            hi--;
    }
    return false;
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    if (sumOfTwoCubes(N)) {
        System.out.println("True");
    }
    else {
        System.out.println("False");
    }
 
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 program for the above approach
import math
 
# Function to check if N can be represented
# as sum of two perfect cubes or not
def sumOfTwoCubes(n):
 
    lo = 1
    hi = round(math.pow(n, 1 / 3))
     
    while (lo <= hi):
        curr = (lo * lo * lo + hi * hi * hi)
        if (curr == n):
             
            # If it is same return true;
            return True
        if (curr < n):
             
            # If the curr smaller than n increment the lo
            lo += 1
        else:
             
            # If the curr is greater than curr decrement
            # the hi
            hi -= 1
     
    return False
 
# Driver Code
N = 28
 
# Function call to check if N
# can be represented as sum of
# two perfect cubes or not
if (sumOfTwoCubes(N)):
    print("True")
else:
    print("False")
     
# This code is contributed by shivanisinghss2110

// C# program for the above approach
using System;
 
class GFG
{
 
// Function to check if N can be represented
// as sum of two perfect cubes or not
static bool sumOfTwoCubes(int n)
{
    int lo = 1, hi = (int)Math.Pow(n, (1.0 / 3.0));
    while (lo <= hi) {
        int curr = (lo * lo * lo + hi * hi * hi);
        if (curr == n)
           
            // if it is same return true;
            return true;
        if (curr < n)
           
            // if the curr smaller than n increment the lo
            lo++;
        else
           
            // if the curr is greater than curr decrement
            // the hi
            hi--;
    }
    return false;
}
 
// Driver Code
public static void Main (String[] args)
{
    int N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    if (sumOfTwoCubes(N)) {
        Console.Write("True");
    }
    else {
        Console.Write("False");
    }
 
}
}
 
// This code is contributed by shivanisinghss2110

<script>
// JavaScript program for the above approach
// Function to check if N can be represented
// as sum of two perfect cubes or not
function sumOfTwoCubes(n)
{
    var lo = 1, hi = (n);
    while (lo <= hi) {
        var curr = (lo * lo * lo + hi * hi * hi);
        if (curr == n)
         
            // if it is same return true;
            return true;
        if (curr < n)
         
            // if the curr smaller than n increment the lo
            lo++;
        else
         
            // if the curr is greater than curr decrement
            // the hi
            hi--;
    }
    return false;
}
 
// Driver Code
    var N = 28;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    if (sumOfTwoCubes(N)) {
        document.write("True");
    }
    else {
        document.write("False");
    }
 
// This code is contributed by shivanisinghss2110
</script>

True

Complejidad de tiempo: O (cbrt (n)), donde n es un número dado 

Complejidad espacial : O(1)