Una Semilla de un número n es un número x tal que la multiplicación de x por sus dígitos es igual a n. La tarea es encontrar todas las semillas de un número dado n. Si no existe ninguna semilla, imprima lo mismo.
Ejemplos:
Input : n = 138 Output : 23 23 is a seed of 138 because 23*2*3 is equal to 138 Input : n = 4977 Output : 79 711 79 is a seed of 4977 because 79 * 7 * 9 = 4977. 711 is also a seed of 4977 because 711 * 1 * 1 * 7 = 4977 Input : n = 9 Output : No seed exists Input : n = 738 Output : 123
Preguntado en Epic
La idea es recorrer todos los números del 1 al n/2. Para cada número que se recorre, encuentre el producto de los dígitos con el número. Una optimización importante realizada en el siguiente programa es evitar volver a calcular los productos de dígitos. Almacenamos los productos en una array. Si ya se ha calculado un producto, lo devolvemos, de lo contrario lo calculamos.
A continuación se muestra la implementación de la idea.
C++
// C++ program to find Seed of a number
#include <bits/stdc++.h>
using namespace std;
const int MAX = 10000;
int prodDig[MAX];
// Stores product of digits of x in prodDig[x]
int getDigitProduct(int x)
{
// If x has single digit
if (x < 10)
return x;
// If digit product is already computed
if (prodDig[x] != 0)
return prodDig[x];
// If digit product is not computed before.
int prod = (x % 10) * getDigitProduct(x/10);
return (prodDig[x] = prod);
}
// Prints all seeds of n
void findSeed(int n)
{
// Find all seeds using prodDig[]
vector<int> res;
for (int i=1; i<=n/2; i++)
if (i*getDigitProduct(i) == n)
res.push_back(i);
// If there was no seed
if (res.size() == 0)
{
cout << "NO seed exists\n";
return;
}
// Print seeds
for (int i=0; i<res.size(); i++)
cout << res[i] << " ";
}
// Driver code
int main()
{
long long int n = 138;
findSeed(n);
return 0;
}
Java
// Java program to find Seed of a number
import java.util.*;
class GFg{
static int MAX = 10000;
static int[] prodDig=new int[MAX];
// Stores product of digits of x in prodDig[x]
static int getDigitProduct(int x)
{
// If x has single digit
if (x < 10)
return x;
// If digit product is already computed
if (prodDig[x] != 0)
return prodDig[x];
// If digit product is not computed before.
int prod = (x % 10) * getDigitProduct(x/10);
return (prodDig[x] = prod);
}
// Prints all seeds of n
static void findSeed(int n)
{
// Find all seeds using prodDig[]
List<Integer> res = new ArrayList<Integer>();
for (int i=1; i<=n/2; i++)
if (i*getDigitProduct(i) == n)
res.add(i);
// If there was no seed
if (res.size() == 0)
{
System.out.println("NO seed exists");
return;
}
// Print seeds
for (int i=0; i<res.size(); i++)
System.out.print(res.get(i)+" ");
}
// Driver code
public static void main(String[] args)
{
int n = 138;
findSeed(n);
}
}
// this code is contributed by mits
Python3
# Python3 program to find Seed of a number
MAX = 10000;
prodDig = [0] * MAX;
# Stores product of digits of
# x in prodDig[x]
def getDigitProduct(x):
# If x has single digit
if (x < 10):
return x;
# If digit product is already computed
if (prodDig[x] != 0):
return prodDig[x];
# If digit product is not computed before.
prod = (int(x % 10) *
getDigitProduct(int(x / 10)));
prodDig[x] = prod;
return prod;
# Prints all seeds of n
def findSeed(n):
# Find all seeds using prodDig[]
res = [];
for i in range(1, int(n / 2 + 2)):
if (i * getDigitProduct(i) == n):
res.append(i);
# If there was no seed
if (len(res) == 0):
print("NO seed exists");
return;
# Print seeds
for i in range(len(res)):
print(res[i], end = " ");
# Driver code
n = 138;
findSeed(n);
# This code is contributed by mits
C#
// C# program to find Seed of a number
using System;
using System.Collections;
class GFG{
static int MAX = 10000;
static int[] prodDig=new int[MAX];
// Stores product of digits of x in prodDig[x]
static int getDigitProduct(int x)
{
// If x has single digit
if (x < 10)
return x;
// If digit product is already computed
if (prodDig[x] != 0)
return prodDig[x];
// If digit product is not computed before.
int prod = (x % 10) * getDigitProduct(x/10);
return (prodDig[x] = prod);
}
// Prints all seeds of n
static void findSeed(int n)
{
// Find all seeds using prodDig[]
ArrayList res = new ArrayList();
for (int i=1; i<=n/2; i++)
if (i*getDigitProduct(i) == n)
res.Add(i);
// If there was no seed
if (res.Count == 0)
{
Console.WriteLine("NO seed exists");
return;
}
// Print seeds
for (int i=0; i<res.Count; i++)
Console.WriteLine(res[i]+" ");
}
// Driver code
static void Main()
{
int n = 138;
findSeed(n);
}
}
// this code is contributed by mits
PHP
<?php
// PHP program to find Seed of a number
$MAX = 10000;
$prodDig = array_fill(0, $MAX, 0);
// Stores product of digits of x in prodDig[x]
function getDigitProduct($x)
{
global $prodDig;
// If x has single digit
if ($x < 10)
return $x;
// If digit product is already computed
if ($prodDig[$x] != 0)
return $prodDig[$x];
// If digit product is not computed before.
$prod = (int)($x % 10) *
getDigitProduct((int)($x / 10));
$prodDig[$x] = $prod;
return $prod;
}
// Prints all seeds of n
function findSeed($n)
{
// Find all seeds using prodDig[]
$res = array();
for ($i = 1; $i <= (int)($n / 2 + 1); $i++)
if ($i * getDigitProduct($i) == $n)
array_push($res, $i);
// If there was no seed
if (count($res) == 0)
{
echo "NO seed exists\n";
return;
}
// Print seeds
for ($i = 0; $i < count($res); $i++)
echo $res[$i] . " ";
}
// Driver code
$n = 138;
findSeed($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find Seed of a number
var MAX = 10000;
var prodDig=Array.from({length: MAX}, (_, i) => 0);
// Stores product of digits of x in prodDig[x]
function getDigitProduct(x)
{
// If x has single digit
if (x < 10)
return x;
// If digit product is already computed
if (prodDig[x] != 0)
return prodDig[x];
// If digit product is not computed before.
var prod = (x % 10) *
getDigitProduct(parseInt(x/10));
return (prodDig[x] = prod);
}
// Prints all seeds of n
function findSeed(n)
{
// Find all seeds using prodDig
var res = [];
for (var i=1; i<=parseInt(n/2); i++)
if (i*getDigitProduct(i) == n)
res.push(i);
// If there was no seed
if (res.length == 0)
{
document.write("NO seed exists");
return;
}
// Print seeds
for (i=0; i<res.length; i++)
document.write(res[i]+" ");
}
// Driver code
var n = 138;
findSeed(n);
// This code is contributed by 29AjayKumar
</script>
Producción :
23
Optimización adicional:
podemos optimizar aún más el código anterior. La idea es hacer una llamada a getDigitProduct(i) solo si i es divisible por n. Consulte https://ide.geeksforgeeks.org/oLYduu para la implementación.
Este artículo es una contribución de Rakesh Kumar . 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 contribuir@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