Dado un entero positivo L , la tarea es encontrar todos los Números de Ramanujan que pueden ser generados por cualquier conjunto de cuádruples (a, b, c, d) , donde 0 < a, b, c, d ≤ L .
Los números de Ramanujan son los números que se pueden expresar como la suma de dos cubos de dos maneras diferentes.
Por lo tanto, Número de Ramanujan (N) = a 3 + b 3 = c 3 + d 3 .
Ejemplos:
Entrada: L = 20
Salida: 1729, 4104
Explicación:
El número 1729 se puede expresar como 12 3 + 1 3 y 10 3 + 9 3 .
El número 4104 se puede expresar como 16 3 + 2 3 y 15 3 + 9 3 .Entrada: L = 30
Salida: 1729, 4104, 13832, 20683
Enfoque ingenuo: el enfoque más simple es verificar todas las combinaciones de cuádruples (a, b, c, d) del rango [1, L] que consisten en elementos distintos que satisfacen la ecuación a 3 + b 3 = c 3 + d 3 . Para los elementos que cumplen las condiciones, almacene los Números de Ramanujan como a 3 + b 3 . Finalmente, después de verificar todas las combinaciones posibles, imprima todos los números almacenados.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find Ramanujan numbers
// made up of cubes of numbers up to L
map<int,vector<int>> ramanujan_On4(int limit)
{
map<int,vector<int>> dictionary;
// Generate all quadruples a, b, c, d
// of integers from the range [1, L]
for(int a = 0; a < limit; a++)
{
for(int b = 0; b < limit; b++)
{
for(int c = 0; c < limit; c++)
{
for(int d = 0; d < limit; d++)
{
// Condition // 2:
// a, b, c, d are not equal
if ((a != b) and (a != c) and (a != d)
and (b != c) and (b != d)
and (c != d)){
int x = pow(a, 3) + pow(b, 3);
int y = pow(c, 3) + pow(d, 3);
if ((x) == (y))
{
int number = pow(a, 3) + pow(b, 3);
dictionary[number] = {a, b, c, d};
}
}
}
}
}
}
// Return all the possible number
return dictionary;
}
// Driver Code
int main()
{
// Given range L
int L = 30;
map<int, vector<int>> ra1_dict = ramanujan_On4(L);
// Print all the generated numbers
for(auto x:ra1_dict)
{
cout << x.first << ": (";
// sort(x.second.begin(),x.second.end());
for(int i = x.second.size() - 1; i >= 0; i--)
{
if(i == 0)
cout << x.second[i] << ")";
else
cout << x.second[i] << ", ";
}
cout << endl;
}
}
// This code is contributed by SURENDRA_GANGWAR.
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
static Map<Integer, List<Integer>> ra1_dict;
// Function to find Ramanujan numbers
// made up of cubes of numbers up to L
static void ramanujan_On4(int limit)
{
// Generate all quadruples a, b, c, d
// of integers from the range [1, L]
for(int a = 0; a < limit; a++)
{
for(int b = 0; b < limit; b++)
{
for(int c = 0; c < limit; c++)
{
for(int d = 0; d < limit; d++)
{
// Condition // 2:
// a, b, c, d are not equal
if ((a != b) && (a != c) && (a != d) &&
(b != c) && (b != d) && (c != d))
{
int x = (int)Math.pow(a, 3) +
(int) Math.pow(b, 3);
int y = (int)Math.pow(c, 3) +
(int) Math.pow(d, 3);
if ((x) == (y))
{
int number = (int)Math.pow(a, 3) +
(int) Math.pow(b, 3);
ra1_dict.put(number, new ArrayList<>(
Arrays.asList(a, b, c, d)));
}
}
}
}
}
}
}
// Driver code
public static void main(String[] args)
{
// Given range L
int L = 30;
ra1_dict = new HashMap<>();
ramanujan_On4(L);
// Print all the generated numbers
for(Map.Entry<Integer,
List<Integer>> x: ra1_dict.entrySet())
{
System.out.print(x.getKey() + ": (");
// sort(x.second.begin(),x.second.end());
for(int i = x.getValue().size() - 1; i >= 0; i--)
{
if (i == 0)
System.out.print(x.getValue().get(i) + ")");
else
System.out.print(x.getValue().get(i) + ", ");
}
System.out.println();
}
}
}
// This code is contributed by offbeat
Python3
# Python program for the above approach
import time
# Function to find Ramanujan numbers
# made up of cubes of numbers up to L
def ramanujan_On4(limit):
dictionary = dict()
# Generate all quadruples a, b, c, d
# of integers from the range [1, L]
for a in range(0, limit):
for b in range(0, limit):
for c in range(0, limit):
for d in range(0, limit):
# Condition # 2:
# a, b, c, d are not equal
if ((a != b) and (a != c) and (a != d)
and (b != c) and (b != d)
and (c != d)):
x = a ** 3 + b ** 3
y = c ** 3 + d ** 3
if (x) == (y):
number = a ** 3 + b ** 3
dictionary[number] = a, b, c, d
# Return all the possible number
return dictionary
# Driver Code
# Given range L
L = 30
ra1_dict = ramanujan_On4(L)
# Print all the generated numbers
for i in sorted(ra1_dict):
print(f'{i}: {ra1_dict[i]}', end ='\n')
Javascript
<script>
// JavaScript program for the above approach
// Function to find Ramanujan numbers
// made up of cubes of numbers up to L
function ramanujan_On4(limit) {
var dictionary = {};
// Generate all quadruples a, b, c, d
// of integers from the range [1, L]
for (var a = 0; a < limit; a++) {
for (var b = 0; b < limit; b++) {
for (var c = 0; c < limit; c++) {
for (var d = 0; d < limit; d++) {
// Condition // 2:
// a, b, c, d are not equal
if (
a !== b &&
a !== c &&
a !== d &&
b !== c &&
b !== d &&
c !== d
) {
var x = Math.pow(a, 3) + Math.pow(b, 3);
var y = Math.pow(c, 3) + Math.pow(d, 3);
if (x == y) {
var number =
Math.pow(a, 3) + Math.pow(b, 3);
dictionary[number] =
[" " + a, " " + b, " " + c, d];
}
}
}
}
}
}
return dictionary;
}
// Driver code
// Given range L
var L = 30;
var ra1_dict = ramanujan_On4(L);
var temp = Object.keys(ra1_dict)
.sort()
.reduce((r, k) => ((r[k] = ra1_dict[k]), r), {});
// Print all the generated numbers
for (const [key, value] of Object.entries(temp)) {
document.write(key + ": (" + value.reverse() + ")" +
"<br>");
}
</script>
Producción:
1729: (9, 10, 1, 12) 4104: (9, 15, 2, 16) 13832: (18, 20, 2, 24) 20683: (19, 24, 10, 27)
Tiempo Complejidad: O(L 4 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos ans[] , para almacenar todos los Números de Ramanujan posibles que satisfagan las condiciones dadas.
- Calcule previamente y almacene los cubos de todos los números del rango [1, L] en una array auxiliar arr[] .
- Inicialice un HashMap , digamos M , que almacene la suma de todas las combinaciones posibles de un par de cubos generados a partir de la array arr[] .
- Ahora, genere todos los pares posibles (i, j) de la array arr[] y, si la suma de pares no existe en la array, marque la ocurrencia de la suma de pares actual en el Mapa . De lo contrario, agregue la suma actual a la array ans[] ya que es uno de los Números de Ramanujan.
- Después de completar los pasos anteriores, imprima los números almacenados en la array ans[] .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find Ramanujan numbers
static HashMap<Integer, ArrayList<Integer> >
ramanujan_On2(int limit)
{
// Stores the cubes from 1 to L
int[] cubes = new int[limit + 1];
for (int i = 0; i <= limit; i++) {
cubes[i] = i * i * i;
}
// Stores the sum of pairs of cubes
HashMap<Integer, ArrayList<Integer> > dict_sum_pairs
= new HashMap<>();
// Stores the Ramanujan Numbers
HashMap<Integer, ArrayList<Integer> >
dict_ramnujan_nums = new HashMap<>();
// Generate all pairs (a, b)
// from the range [0, L]
for (int a = 0; a <= limit; a++) {
for (int b = a + 1; b <= limit; b++) {
int a3 = cubes[a];
int b3 = cubes[b];
// Find the sum of pairs
int sum_pairs = a3 + b3;
// Add to Map
if (dict_sum_pairs.containsKey(sum_pairs))
{
// If the current sum_pair is already in
// the sum_pair Map, then store store
// all numbers in ramnujan_no map
int c
= dict_sum_pairs.get(sum_pairs).get(
0);
int d
= dict_sum_pairs.get(sum_pairs).get(
1);
dict_ramnujan_nums.put(
sum_pairs,
new ArrayList<>(
Arrays.asList(a, b, c, d)));
}
else
{
// otherwise add in sum_pair map
dict_sum_pairs.put(
sum_pairs,
new ArrayList<>(
Arrays.asList(a, b)));
}
}
}
// Return possible ramanujan numbers
return dict_ramnujan_nums;
}
// Driver code
public static void main(String[] args)
{
// Given range L
int L = 30;
HashMap<Integer, ArrayList<Integer> > r_dict
= ramanujan_On2(L);
// Print all the generated numbers
for (Map.Entry<Integer, ArrayList<Integer> > e :
(Iterable<
Map.Entry<Integer, ArrayList<Integer> > >)
r_dict.entrySet()
.stream()
.sorted(
Map.Entry
.comparingByKey())::iterator) {
System.out.print(e.getKey() + ": (");
for (int i = 0; i <= e.getValue().size() - 1;
i++) {
if (i == e.getValue().size() - 1)
System.out.print(e.getValue().get(i)
+ ")");
else
System.out.print(e.getValue().get(i)
+ ", ");
}
System.out.println();
}
}
}
// This code is contributed by Karandeep1234
Python3
# Python program for the above approach
from array import *
import time
# Function to find Ramanujan numbers
# made up of cubes of numbers up to L
def ramanujan_On2(limit):
cubes = array('i', [])
# Stores the sum of pairs of cubes
dict_sum_pairs = dict()
# Stores the Ramanujan Numbers
dict_ramnujan_nums = dict()
sum_pairs = 0
# Stores the cubes from 1 to L
for i in range(0, limit):
cubes.append(i ** 3)
# Generate all pairs (a, b)
# from the range [0, L]
for a in range(0, limit):
for b in range(a + 1, limit):
a3, b3 = cubes[a], cubes[b]
# Find the sum of pairs
sum_pairs = a3 + b3
# Append to dictionary
if sum_pairs in dict_sum_pairs:
# If the current sum is in
# the dictionary, then store
# the current number
c, d = dict_sum_pairs.get(sum_pairs)
dict_ramnujan_nums[sum_pairs] = a, b, c, d
# Otherwise append the current
# sum pairs to the sum pairs
# dictionary
else:
dict_sum_pairs[sum_pairs] = a, b
# Return the possible Ramanujan
# Numbers
return dict_ramnujan_nums
# Driver Code
# Given range L
L = 30
r_dict = ramanujan_On2(L)
# Print all the numbers
for d in sorted(r_dict):
print(f'{d}: {r_dict[d]}', end ='\n')
Producción:
1729: (9, 10, 1, 12) 4104: (9, 15, 2, 16) 13832: (18, 20, 2, 24) 20683: (19, 24, 10, 27)
Complejidad Temporal: O(L 2 )
Espacio Auxiliar: O(L 2 )
Publicación traducida automáticamente
Artículo escrito por kumar_pankaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA