Dado un número n, encuentre dos pares que puedan representar el número como la suma de dos cubos. En otras palabras, encuentre dos pares (a, b) y (c, d) tales que el número n dado se pueda expresar como
n = a^3 + b^3 = c^3 + d^3
donde a, b, c y d son cuatro números distintos.
Ejemplos:
Input: n = 1729 Output: (1, 12) and (9, 10) Explanation: 1729 = 1^3 + 12^3 = 9^3 + 10^3 Input: n = 4104 Output: (2, 16) and (9, 15) Explanation: 4104 = 2^3 + 16^3 = 9^3 + 15^3 Input: n = 13832 Output: (2, 24) and (18, 20) Explanation: 13832 = 2^3 + 24^3 = 18^3 + 20^3
Hemos discutido una solución O ( n 2/3 ) en el siguiente conjunto 1.
Encuentra pares de cubos | Conjunto 1 (Una solución n^(2/3)) En esta publicación, se discute una solución
O( n 1/3 ).
Cualquier número n que satisfaga la restricción tendrá dos pares distintos (a, b) y (c, d) tales que a, b, c y d son todos menores que n 1/3 . La idea es crear una array auxiliar de tamaño n 1/3 . Cada índice i en la array almacenará un valor igual al cubo de ese índice, es decir, arr[i] = i^3. Ahora el problema se reduce a encontrar un par de elementos en una array ordenada cuya suma sea igual al número n dado. El problema se discute en detalle aquí .
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find pairs that can represent
// the given number as sum of two cubes
#include <iostream>
#include <cmath>
using namespace std;
// Function to find pairs that can represent
// the given number as sum of two cubes
void findPairs(int n)
{
// find cube root of n
int cubeRoot = pow(n, 1.0 / 3.0);
// create a array of size of size 'cubeRoot'
int cube[cubeRoot + 1];
// for index i, cube[i] will contain i^3
for (int i = 1; i <= cubeRoot; i++)
cube[i] = i*i*i;
// Find all pairs in above sorted
// array cube[] whose sum is equal to n
int l = 1;
int r = cubeRoot;
while (l < r)
{
if (cube[l] + cube[r] < n)
l++;
else if(cube[l] + cube[r] > n)
r--;
else {
cout << "(" << l << ", " << r
<< ")" << endl;
l++; r--;
}
}
}
// Driver function
int main()
{
int n = 20683;
findPairs(n);
return 0;
}
Java
// Java program to find pairs
// that can represent the given
// number as sum of two cubes
import java.io.*;
class GFG
{
// Function to find pairs
// that can represent the
// given number as sum of
// two cubes
static void findPairs(int n)
{
// find cube root of n
int cubeRoot = (int)Math.pow(
n, 1.0 / 3.0);
// create a array of
// size of size 'cubeRoot'
int cube[] = new int[cubeRoot + 1];
// for index i, cube[i]
// will contain i^3
for (int i = 1; i <= cubeRoot; i++)
cube[i] = i * i * i;
// Find all pairs in above
// sorted array cube[]
// whose sum is equal to n
int l = 1;
int r = cubeRoot;
while (l < r)
{
if (cube[l] + cube[r] < n)
l++;
else if(cube[l] + cube[r] > n)
r--;
else {
System.out.println("(" + l +
", " + r +
")" );
l++; r--;
}
}
}
// Driver Code
public static void main (String[] args)
{
int n = 20683;
findPairs(n);
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to find pairs that
# can represent the given number
# as sum of two cubes
import math
# Function to find pairs that can
# represent the given number as
# sum of two cubes
def findPairs( n):
# find cube root of n
cubeRoot = int(math.pow(n, 1.0 / 3.0));
# create a array of
# size of size 'cubeRoot'
cube = [0] * (cubeRoot + 1);
# for index i, cube[i]
# will contain i^3
for i in range(1, cubeRoot + 1):
cube[i] = i * i * i;
# Find all pairs in above sorted
# array cube[] whose sum
# is equal to n
l = 1;
r = cubeRoot;
while (l < r):
if (cube[l] + cube[r] < n):
l += 1;
else if(cube[l] + cube[r] > n):
r -= 1;
else:
print("(" , l , ", " , math.floor(r),
")", end = "");
print();
l += 1;
r -= 1;
# Driver code
n = 20683;
findPairs(n);
# This code is contributed by mits
C#
// C# program to find pairs
// that can represent the given
// number as sum of two cubes
using System;
class GFG
{
// Function to find pairs
// that can represent the
// given number as sum of
// two cubes
static void findPairs(int n)
{
// find cube root of n
int cubeRoot = (int)Math.Pow(n, 1.0 /
3.0);
// create a array of
// size of size 'cubeRoot'
int []cube = new int[cubeRoot + 1];
// for index i, cube[i]
// will contain i^3
for (int i = 1; i <= cubeRoot; i++)
cube[i] = i * i * i;
// Find all pairs in above
// sorted array cube[]
// whose sum is equal to n
int l = 1;
int r = cubeRoot;
while (l < r)
{
if (cube[l] + cube[r] < n)
l++;
else if(cube[l] + cube[r] > n)
r--;
else {
Console.WriteLine("(" + l +
", " + r +
")" );
l++; r--;
}
}
}
// Driver Code
public static void Main ()
{
int n = 20683;
findPairs(n);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find pairs
// that can represent the
// given number as sum of
// two cubes
// Function to find pairs
// that can represent the
// given number as sum of
// two cubes
function findPairs( $n)
{
// find cube root of n
$cubeRoot = pow($n, 1.0 / 3.0);
// create a array of
// size of size 'cubeRoot'
$cube = array();
// for index i, cube[i]
// will contain i^3
for ($i = 1; $i <= $cubeRoot; $i++)
$cube[$i] = $i * $i * $i;
// Find all pairs in above sorted
// array cube[] whose sum
// is equal to n
$l = 1;
$r = $cubeRoot;
while ($l < $r)
{
if ($cube[$l] + $cube[$r] <$n)
$l++;
else if($cube[$l] + $cube[$r] > $n)
$r--;
else
{
echo "(" , $l , ", " , floor($r)
, ")" ;
echo "\n";
$l++;$r--;
}
}
}
// Driver code
$n = 20683;
findPairs($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find pairs
// that can represent the given
// number as sum of two cubes
// Function to find pairs
// that can represent the
// given number as sum of
// two cubes
function findPairs(n)
{
// find cube root of n
var cubeRoot = parseInt(Math.pow(
n, 1.0 / 3.0));
// create a array of
// size of size 'cubeRoot'
var cube = Array.from({length: cubeRoot + 1}, (_, i) => 0);
// for index i, cube[i]
// will contain i^3
for (i = 1; i <= cubeRoot; i++)
cube[i] = i * i * i;
// Find all pairs in above
// sorted array cube
// whose sum is equal to n
var l = 1;
var r = cubeRoot;
while (l < r)
{
if (cube[l] + cube[r] < n)
l++;
else if(cube[l] + cube[r] > n)
r--;
else {
document.write("(" + l +
", " + r +
")<br>" );
l++; r--;
}
}
}
// Driver Code
var n = 20683;
findPairs(n);
// This code is contributed by Amit Katiyar
</script>
Producción:
(10, 27) (19, 24)
La complejidad temporal de la solución anterior es O(n^(1/3)).
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA