Dado un número entero positivo N , la tarea es verificar si el número dado N se puede representar como el producto de dos cubos perfectos positivos o no. Si es posible, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: N = 216
Salida: Sí
Explicación:
El número dado N(= 216) se puede representar como 8 * 27 = 2 3 * 3 3 .
Por lo tanto, imprima Sí.Entrada: N = 10
Salida: No
Enfoque: el enfoque más simple para resolver el problema dado es almacenar los cubos perfectos de todos los números desde 1 hasta la raíz cúbica de N en un mapa y verificar si N se puede representar como el producto de dos números presentes en el mapa o no .
Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa ordenado , digamos cubos , que almacene los cubos perfectos en orden ordenado.
- Recorra el mapa y verifique si existe algún par cuyo producto sea N , luego imprima «Sí» . De lo contrario, escriba “No” .
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 N can
// be represented as the product
// of two perfect cubes or not
void productOfTwoPerfectCubes(int N)
{
// Stores the perfect cubes
map<int, int> cubes;
for (int i = 1;
i * i * i <= N; i++)
cubes[i * i * i] = i;
// Traverse the Map
for (auto itr = cubes.begin();
itr != cubes.end();
itr++) {
// Stores the first number
int firstNumber = itr->first;
if (N % itr->first == 0) {
// Stores the second number
int secondNumber = N / itr->first;
// Search the pair for the
// first number to obtain
// product N from the Map
if (cubes.find(secondNumber)
!= cubes.end()) {
cout << "Yes";
return;
}
}
}
// If N cannot be represented
// as the product of the two
// positive perfect cubes
cout << "No";
}
// Driver Code
int main()
{
int N = 216;
productOfTwoPerfectCubes(N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if N can
// be represented as the product
// of two perfect cubes or not
static void productOfTwoPerfectCubes(int N)
{
// Stores the perfect cubes
Map<Integer, Integer> cubes = new HashMap<>();
for(int i = 1; i * i * i <= N; i++)
cubes.put(i * i * i,i);
// Traverse the Map
for(Map.Entry<Integer,
Integer> itr: cubes.entrySet())
{
// Stores the first number
int firstNumber = itr.getKey();
if (N % itr.getKey() == 0)
{
// Stores the second number
int secondNumber = N / itr.getKey();
// Search the pair for the
// first number to obtain
// product N from the Map
if (cubes.containsKey(secondNumber))
{
System.out.println("Yes");
return;
}
}
}
// If N cannot be represented
// as the product of the two
// positive perfect cubes
System.out.println("No");
}
// Driver code
public static void main(String[] args)
{
int N = 216;
productOfTwoPerfectCubes(N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to check if N can
# be represented as the product
# of two perfect cubes or not
def productOfTwoPerfectCubes(N):
# Stores the perfect cubes
cubes = {}
i = 1
while i * i * i <= N:
cubes[i * i * i] = i
i += 1
# Traverse the Map
for itr in cubes:
# Stores the first number
firstNumber = itr
if (N % itr == 0):
# Stores the second number
secondNumber = N // itr
# Search the pair for the
# first number to obtain
# product N from the Map
if (secondNumber in cubes):
print("Yes")
return
# If N cannot be represented
# as the product of the two
# positive perfect cubes
print("No")
# Driver Code
if __name__ == "__main__":
N = 216
productOfTwoPerfectCubes(N)
# This code is contributed by mohit ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if N can
// be represented as the product
// of two perfect cubes or not
static void productOfTwoPerfectCubes(int N)
{
// Stores the perfect cubes
Dictionary<int,int> cubes = new Dictionary<int,int>();
for (int i = 1; i * i * i <= N; i++){
cubes.Add(i * i * i, i);
}
// Traverse the Map
foreach(KeyValuePair<int, int> kvp in cubes)
{
// Stores the first number
int firstNumber = kvp.Key;
if (N % kvp.Key == 0) {
// Stores the second number
int secondNumber = N / kvp.Key;
// Search the pair for the
// first number to obtain
// product N from the Map
if (cubes.ContainsKey(secondNumber)) {
Console.Write("Yes");
return;
}
}
}
// If N cannot be represented
// as the product of the two
// positive perfect cubes
Console.Write("No");
}
// Driver Code
public static void Main()
{
int N = 216;
productOfTwoPerfectCubes(N);
}
}
// This code is contributed by ipg2016107..
Javascript
<script>
// Javascript program for the above approach
// Function to check if N can
// be represented as the product
// of two perfect cubes or not
function productOfTwoPerfectCubes(N)
{
// Stores the perfect cubes
let cubes = new Map();
for(let i = 1; i * i * i <= N; i++)
cubes.set(i * i * i, i);
// Traverse the Map
for(let [key, value] of cubes.entries())
{
// Stores the first number
let firstNumber = key;
if (N % key == 0)
{
// Stores the second number
let secondNumber = N / key;
// Search the pair for the
// first number to obtain
// product N from the Map
if (cubes.has(secondNumber))
{
document.write("Yes<br>");
return;
}
}
}
// If N cannot be represented
// as the product of the two
// positive perfect cubes
document.write("No<br>");
}
// Driver code
let N = 216;
productOfTwoPerfectCubes(N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Yes
Complejidad de tiempo: O(N 1/3 * log(N))
Espacio auxiliar: O(N 1/3 )
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de la observación de que solo los cubos perfectos se pueden representar como un producto de 2 cubos perfectos.
Sean x e y los dos números tales que x 3 * y 3 = N— (1) La
ecuación (1) se puede escribir como:
=> (x*y) 3 = N
Tomando raíz cúbica en ambos lados,
=> x* y = (N) 1/3 — (2)
Para que la ecuación (2) sea verdadera, N debe ser un cubo perfecto.
Entonces, el problema se reduce a comprobar si N es un cubo perfecto o no . Si es cierto, escriba «Sí» , de lo contrario, «No» .
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 number N
// can be represented as the product
// of two perfect cubes or not
void productOfTwoPerfectCubes(int N)
{
int cube_root;
cube_root = round(cbrt(N));
// If cube of cube_root is N
if (cube_root * cube_root
* cube_root
== N) {
cout << "Yes";
return;
}
// Otherwise, print No
else {
cout << "No";
return;
}
}
// Driver Code
int main()
{
int N = 216;
productOfTwoPerfectCubes(N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
class GFG{
// Function to check if the number N
// can be represented as the product
// of two perfect cubes or not
public static void productOfTwoPerfectCubes(double N)
{
double cube_root;
cube_root = Math.round(Math.cbrt(N));
// If cube of cube_root is N
if (cube_root * cube_root * cube_root == N)
{
System.out.println("Yes");
return;
}
// Otherwise, print No
else
{
System.out.println("No");
return;
}
}
// Driver Code
public static void main(String args[])
{
double N = 216;
productOfTwoPerfectCubes(N);
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach
# Function to check if the number N
# can be represented as the product
# of two perfect cubes or not
def productOfTwoPerfectCubes(N):
cube_root = round((N) ** (1 / 3))
print(cube_root)
# If cube of cube_root is N
if (cube_root * cube_root * cube_root == N):
print("Yes")
return
# Otherwise, print No
else:
print("No")
return
# Driver Code
if __name__ == '__main__':
N = 216
productOfTwoPerfectCubes(N)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to check if the number N
// can be represented as the product
// of two perfect cubes or not
public static void productOfTwoPerfectCubes(double N)
{
double cube_root;
cube_root = Math.Round(Math.Cbrt(N));
// If cube of cube_root is N
if (cube_root * cube_root * cube_root == N)
{
Console.Write("Yes");
return;
}
// Otherwise, print No
else
{
Console.Write("No");
return;
}
}
// Driver Code
static public void Main()
{
double N = 216;
productOfTwoPerfectCubes(N);
}
}
// This code is contributed by mohit kumar 29.
Javascript
<script>
// Javascript program for the above approach
// Function to check if the number N
// can be represented as the product
// of two perfect cubes or not
function productOfTwoPerfectCubes(N)
{
var cube_root;
cube_root = Math.round(Math.cbrt(N));
// If cube of cube_root is N
if (cube_root * cube_root * cube_root == N)
{
document.write("Yes");
return;
}
// Otherwise, print No
else
{
document.write("No");
return;
}
}
// Driver code
var N = 216;
productOfTwoPerfectCubes(N);
// This code is contributed by Ankita saini
</script>
Producción:
Yes
Complejidad de Tiempo: O(N 1/3 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por babayaga18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA