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
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 muy simple. Para cada par distinto (x, y) formado por números menores que n 1/3 , si su suma (x 3 + y 3 ) es igual al número dado, los almacenamos en una tabla hash usando sum como clave. Si vuelven a aparecer pares con suma igual al número dado, simplemente imprimimos ambos pares.
1) Create an empty hash map, say s.
2) cubeRoot = n1/3
3) for (int x = 1; x < cubeRoot; x++)
for (int y = x + 1; y <= cubeRoot; y++)
int sum = x3 + y3;
if (sum != n) continue;
if sum exists in s,
we found two pairs with sum, print the pairs
else
insert pair(x, y) in s using sum as key
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 <bits/stdc++.h>
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 an empty map
unordered_map<int, pair<int, int> > s;
// Consider all pairs such with values less
// than cuberoot
for (int x = 1; x < cubeRoot; x++)
{
for (int y = x + 1; y <= cubeRoot; y++)
{
// find sum of current pair (x, y)
int sum = x*x*x + y*y*y;
// do nothing if sum is not equal to
// given number
if (sum != n)
continue;
// if sum is seen before, we found two pairs
if (s.find(sum) != s.end())
{
cout << "(" << s[sum].first << ", "
<< s[sum].second << ") and ("
<< x << ", " << y << ")" << endl;
}
else
// if sum is seen for the first time
s[sum] = make_pair(x, y);
}
}
}
// Driver function
int main()
{
int n = 13832;
findPairs(n);
return 0;
}
Java
// Java program to find pairs that can represent
// the given number as sum of two cubes
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// 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 an empty map
HashMap<Integer, pair> s = new HashMap<Integer, pair>();
// Consider all pairs such with values less
// than cuberoot
for (int x = 1; x < cubeRoot; x++)
{
for (int y = x + 1; y <= cubeRoot; y++)
{
// find sum of current pair (x, y)
int sum = x*x*x + y*y*y;
// do nothing if sum is not equal to
// given number
if (sum != n)
continue;
// if sum is seen before, we found two pairs
if (s.containsKey(sum))
{
System.out.print("(" + s.get(sum).first+ ", "
+ s.get(sum).second+ ") and ("
+ x+ ", " + y+ ")" +"\n");
}
else
// if sum is seen for the first time
s.put(sum, new pair(x, y));
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 13832;
findPairs(n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 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
def findPairs(n):
# Find cube root of n
cubeRoot = pow(n, 1.0 / 3.0);
# Create an empty map
s = {}
# Consider all pairs such with
# values less than cuberoot
for x in range(int(cubeRoot)):
for y in range(x + 1,
int(cubeRoot) + 1):
# Find sum of current pair (x, y)
sum = x * x * x + y * y * y;
# Do nothing if sum is not equal to
# given number
if (sum != n):
continue;
# If sum is seen before, we
# found two pairs
if sum in s.keys():
print("(" + str(s[sum][0]) +
", " + str(s[sum][1]) +
") and (" + str(x) +
", " + str(y) +
")" + "\n")
else:
# If sum is seen for the first time
s[sum] = [x, y]
# Driver code
if __name__=="__main__":
n = 13832
findPairs(n)
# This code is contributed by rutvik_56
C#
// C# program to find pairs that can represent
// the given number as sum of two cubes
using System;
using System.Collections.Generic;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// 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 an empty map
Dictionary<int, pair> s = new Dictionary<int, pair>();
// Consider all pairs such with values less
// than cuberoot
for (int x = 1; x < cubeRoot; x++)
{
for (int y = x + 1; y <= cubeRoot; y++)
{
// find sum of current pair (x, y)
int sum = x*x*x + y*y*y;
// do nothing if sum is not equal to
// given number
if (sum != n)
continue;
// if sum is seen before, we found two pairs
if (s.ContainsKey(sum))
{
Console.Write("(" + s[sum].first+ ", "
+ s[sum].second+ ") and ("
+ x+ ", " + y+ ")" +"\n");
}
else
// if sum is seen for the first time
s.Add(sum, new pair(x, y));
}
}
}
// Driver code
public static void Main(String[] args)
{
int n = 13832;
findPairs(n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
// 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
let cubeRoot = Math.floor(Math.pow(n, 1/3));
// create an empty map
let s = new Map();
// Consider all pairs such with values less
// than cuberoot
for (let x = 1; x < cubeRoot; x++){
for (let y = x + 1; y <= cubeRoot; y++){
// find sum of current pair (x, y)
let sum = x*x*x + y*y*y;
// do nothing if sum is not equal to
// given number
if (sum != n){
continue;
}
// if sum is seen before, we found two pairs
if (s.has(sum)){
console.log("(", s.get(sum)[0], ",", s.get(sum)[1], ") and (",x,"," ,y,")");
}
else{
// if sum is seen for the first time
s.set(sum, [x, y]);
}
}
}
}
// Driver function
{
let n = 13832;
findPairs(n);
}
// The code is contributed by Gautam goel (gautamgoel962)
Producción:
(2, 24) and (18, 20)
La complejidad del tiempo de la solución anterior es O (n 2/3 ), que es mucho menor que O (n).
¿ Podemos resolver el problema anterior en tiempo O (n 1/3 )? Hablaremos de eso en la próxima publicación.
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