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

Dado un entero positivo N , la tarea es verificar si N puede representarse como la diferencia entre dos cubos perfectos positivos o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: N = 124
Salida: Sí
Explicación: Dado que 124 se puede representar como (125 – 1) = (5 ³ – 1 ³ ). Por lo tanto, imprima Sí.

Entrada: N = 4
Salida: No

Enfoque: La idea para resolver el problema dado es almacenar los cubos perfectos de todos los números del 1 al X , donde X es el entero máximo para el cual la diferencia entre X ³ y (X – 1) ³ es como máximo N , en un Mapee y verifique si N se puede representar como la diferencia de dos números presentes en el Map 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 X números naturales en orden ordenado.
• Recorra el mapa y verifique que el par tenga una diferencia igual a N . Si existe tal par, 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 the number N
// can be represented as a difference
// between two perfect cubes or not
void differenceOfTwoPerfectCubes(int N)
{
    // Stores the perfect cubes
    // of first X natural numbers
    map<int, int> cubes;
 
    for (int i = 1;
         (i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N;
         i++) {
 
        cubes[i * i * i] = 1;
    }
 
    map<int, int>::iterator itr;
 
    // Traverse the map
    for (itr = cubes.begin(); itr != cubes.end(); itr++) {
 
        // Stores the first number
        int firstNumber = itr->first;
 
        // Stores the second number
        int secondNumber = N + itr->first;
 
        // Search the pair for the second
        // number to obtain difference N
        // from the Map
        if (cubes.find(secondNumber) != cubes.end()) {
            cout << "Yes";
            return;
        }
    }
 
    // If N cannot be represented
    // as difference between two
    // positive perfect cubes
    cout << "No";
}
 
// Driver Code
int main()
{
    int N = 124;
    differenceOfTwoPerfectCubes(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to check if N can be represented
  // as difference of two perfect cubes or not
  public static void differenceOfTwoPerfectCubes(int N)
  {
 
    // Stores the perfect cubes
    // of first N natural numbers
    HashMap<Integer, Integer> cubes = new HashMap<>();
    for (int i = 1; (i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N; i++)
      cubes.put((i * i * i), 1);
 
    // 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 second
      // number to obtain difference N from the Map
      if (cubes.containsKey(secondNumber))
      {
        System.out.println("Yes");
        return;
      }
    }
 
    // If N cannot be represented as
    // difference of two positive perfect cubes
    System.out.println("No");
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 124;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    differenceOfTwoPerfectCubes(N);
  }
}
 
// This code is contributed by shailjapriya.

# Python3 program for the above approach
 
# Function to check if the number N
# can be represented as a difference
# between two perfect cubes or not
def differenceOfTwoPerfectCubes(N):
 
    # Stores the perfect cubes
    # of first X natural numbers
    cubes = {}
 
    i = 1
    while ((i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N):
        cubes[i * i * i] = 1
        i += 1
 
    # Traverse the map
    for itr in cubes.keys():
 
        # Stores the first number
        firstNumber = itr
 
        # Stores the second number
        secondNumber = N + itr
 
        # Search the pair for the second
        # number to obtain difference N
        # from the Map
        if ((secondNumber) in cubes):
            print("Yes")
            return
 
    # If N cannot be represented
    # as difference between two
    # positive perfect cubes
    print("No")
 
# Driver Code
if __name__ == "__main__":
 
    N = 124
    differenceOfTwoPerfectCubes(N)
 
    # This code is contributed by ukasp.

// 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 difference of two perfect cubes or not
public static void differenceOfTwoPerfectCubes(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) - ((i - 1) *
            (i - 1) * (i - 1)) <= N;
            i++)
        cubes.Add((i * i * i), 1);
 
    // Traverse the map
    foreach(KeyValuePair<int, int> entry in cubes)
    {
         
        // Stores first number
        int firstNumber = entry.Key;
 
        // Stores second number
        int secondNumber = N + entry.Key;
 
        // Search the pair for the second
        // number to obtain difference N from the Map
        if (cubes.ContainsKey(secondNumber))
        {
            Console.Write("Yes");
            return;
        }
    }
 
    // If N cannot be represented as
    // difference of two positive perfect cubes
    Console.Write("No");
}
 
// Driver code
static void Main()
{
    int N = 124;
 
    // Function call to check if N
    // can be represented as
    // sum of two perfect cubes or not
    differenceOfTwoPerfectCubes(N);
}
}
 
// This code is contributed by abhinavjain194

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

Yes

Complejidad de tiempo: O(∛N*log N)
Espacio auxiliar: O(∛N)