Seeds (Or Seed Roots) of a number
A Seed of a number n is a number x such that multiplication of x with its digits is equal to n. The task is to find all seeds of a given number n. If no seed exists, then print the same.
Examples:
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
Asked in Epic
The idea is to traverse all numbers from 1 to n/2. For every number being traversed, find product of digits with the number. An important optimization done in below program is to avoid re-computations of digit products. We store the products in an array. If a product has already been computed, we return it, else we compute it.
Below is the implementation of the 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> |
Output :
23
Further Optimization :
We can further optimize above code. The idea is to make a call to getDigitProduct(i) only if i is divisible by n. Please refer https://ide.w3wiki.net/oLYduu for implementation.
Contact Us