Comprueba si un número se puede representar como la suma de dos bicuadrados perfectos positivos

Dado un entero positivo N , la tarea es comprobar si N puede escribirse como la suma de dos bicuadrados perfectos o no, es decir, (N = X ⁴ + Y ⁴ ), donde X e Y son enteros no negativos . Si es posible, imprima Sí . De lo contrario, imprima No.

Ejemplos:

Entrada: N = 97
Salida: Sí
Explicación: La suma de los bicuadrados de 2 y 3 es 97, es decir, 2 ⁴ + 3 ⁴ = 16 + 81 = 97(= N).

Entrada: N =7857
Salida: Sí

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es considerar todas las combinaciones posibles de números enteros X e Y y verificar si la suma de sus bicuadrados es igual a N o no. Si se encuentra que es cierto, escriba Sí . De lo contrario, imprima No.

Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el enfoque de dos punteros , la idea es encontrar los dos números en el rango $(0, \sqrt[4]{N})$ . Siga el siguiente paso para resolver este problema:

Inicialice dos punteros, digamos i como 0 y j como $\sqrt[4]{N}$ .
Iterar un bucle hasta que j sea menor que i y realizar los siguientes pasos:
- Si el valor de j ⁴ es N y i ⁴ es N , imprima Sí .
- Si el valor de (i ⁴ + i ⁴ ) o (j ⁴ + j ⁴ ) o (i ⁴ + j ⁴ ) es N , entonces imprima Sí .
- Si el valor de (i ⁴ + j ⁴ ) es menor que N , entonces incremente el puntero i en 1 . De lo contrario, disminuya el puntero j en 1 .
Después de completar los pasos anteriores, si los bucles terminan, imprima No , ya que no existen tales pares que satisfagan los criterios dados.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the given number
// N can be expressed as the sum of two
// biquadrates or not
string sumOfTwoBiquadrates(int N)
{
    // Base Case
    if (N == 0)
        return "Yes";
 
    // Find the range to traverse
    int j = floor(sqrt(sqrt(N)));
    int i = 1;
 
    while (i <= j) {
 
        // If x & y exists
        if (j * j * j * j == N)
            return "Yes";
        if (i * i * i * i == N)
            return "Yes";
        if (i * i * i * i
                + j * j * j * j
            == N)
            return "Yes";
 
        // If sum of powers of i and j
        // of 4 is less than N, then
        // increment the value of i
        if (i * i * i * i
                + j * j * j * j
            < N)
            i++;
 
        // Otherwise, decrement the
        // value of j
        else
            j--;
    }
 
    // If no such pairs exist
    return "No";
}
 
// Driver Code
int main()
{
    int N = 7857;
    cout << sumOfTwoBiquadrates(N);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG
{
   
// Function to check if the given number
// N can be expressed as the sum of two
// biquadrates or not
static String sumOfTwoBiquadrates(int N)
{
   
    // Base Case
    if (N == 0)
        return "Yes";
 
    // Find the range to traverse
    int j = (int)Math.floor((double)(Math.sqrt((int)(Math.sqrt(N)))));
  
    int i = 1;
 
    while (i <= j) {
 
        // If x & y exists
        if (j * j * j * j == N)
            return "Yes";
        if (i * i * i * i == N)
            return "Yes";
        if (i * i * i * i
                + j * j * j * j
            == N)
            return "Yes";
 
        // If sum of powers of i and j
        // of 4 is less than N, then
        // increment the value of i
        if (i * i * i * i
                + j * j * j * j
            < N)
            i++;
 
        // Otherwise, decrement the
        // value of j
        else
            j--;
    }
 
    // If no such pairs exist
    return "No";
}
 
// Driver Code
public static void main(String []args)
{
    int N = 7857;
    System.out.println(sumOfTwoBiquadrates(N));
 
   
}}
 
// This code is contributed by AnkThon

Python3

# python program for the above approach
import math
 
# Function to check if the given number
# N can be expressed as the sum of two
# biquadrates or not
def sumOfTwoBiquadrates(N):
 
    # Base Case
    if (N == 0):
        return "Yes"
 
    # Find the range to traverse
    j = int(math.sqrt(math.sqrt(N)))
    i = 1
 
    while (i <= j):
 
        # If x & y exists
        if (j * j * j * j == N):
            return "Yes"
        if (i * i * i * i == N):
            return "Yes"
        if (i * i * i * i + j * j * j * j == N):
            return "Yes"
 
        # If sum of powers of i and j
        # of 4 is less than N, then
        # increment the value of i
        if (i * i * i * i + j * j * j * j < N):
            i += 1
 
        # Otherwise, decrement the
        # value of j
        else:
            j -= 1
 
    # If no such pairs exist
    return "No"
 
# Driver Code
if __name__ == "__main__":
 
    N = 7857
    print(sumOfTwoBiquadrates(N))
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
class GFG
{
   
// Function to check if the given number
// N can be expressed as the sum of two
// biquadrates or not
static string sumOfTwoBiquadrates(int N)
{
   
    // Base Case
    if (N == 0)
        return "Yes";
 
    // Find the range to traverse
    int j = (int)Math.Floor((double)(Math.Sqrt((int)(Math.Sqrt(N)))));
  
    int i = 1;
 
    while (i <= j) {
 
        // If x & y exists
        if (j * j * j * j == N)
            return "Yes";
        if (i * i * i * i == N)
            return "Yes";
        if (i * i * i * i
                + j * j * j * j
            == N)
            return "Yes";
 
        // If sum of powers of i and j
        // of 4 is less than N, then
        // increment the value of i
        if (i * i * i * i
                + j * j * j * j
            < N)
            i++;
 
        // Otherwise, decrement the
        // value of j
        else
            j--;
    }
 
    // If no such pairs exist
    return "No";
}
 
// Driver Code
public static void Main()
{
    int N = 7857;
    Console.WriteLine(sumOfTwoBiquadrates(N));
 
   
}}
 
// This code is contributed by ukasp.

Javascript

<script>
// Javascript program for the above approach
 
// Function to check if the given number
// N can be expressed as the sum of two
// biquadrates or not
function sumOfTwoBiquadrates(N)
{
 
  // Base Case
  if (N == 0) return "Yes";
 
  // Find the range to traverse
  let j = Math.floor(Math.sqrt(Math.sqrt(N)));
  let i = 1;
 
  while (i <= j)
  {
   
    // If x & y exists
    if (j * j * j * j == N) return "Yes";
    if (i * i * i * i == N) return "Yes";
    if (i * i * i * i + j * j * j * j == N) return "Yes";
 
    // If sum of powers of i and j
    // of 4 is less than N, then
    // increment the value of i
    if (i * i * i * i + j * j * j * j < N) i++;
     
    // Otherwise, decrement the
    // value of j
    else j--;
  }
 
  // If no such pairs exist
  return "No";
}
 
// Driver Code
 
let N = 7857;
document.write(sumOfTwoBiquadrates(N));
 
// This code is contributed by gfgking.
</script>

Producción:

Yes

Complejidad Temporal: $O(\sqrt[4]{N})$
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por shuvonmajhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta