Find the smallest number whose digits multiply to a given number n
Given a number ‘n’, find the smallest number ‘p’ such that if we multiply all digits of ‘p’, we get ‘n’. The result ‘p’ should have minimum two digits.
Examples:
Input: n = 36 Output: p = 49 // Note that 4*9 = 36 and 49 is the smallest such number Input: n = 100 Output: p = 455 // Note that 4*5*5 = 100 and 455 is the smallest such number Input: n = 1 Output:p = 11 // Note that 1*1 = 1 Input: n = 13 Output: Not Possible
For a given n, following are the two cases to be considered.
Case 1: n < 10 When n is smaller than 10, the output is always n+10. For example for n = 7, the output is 17. For n = 9, output is 19.
Case 2: n >= 10 Find all factors of n which are between 2 and 9 (both inclusive). The idea is to start searching from 9 so that the number of digits in the result is minimized. For example, 9 is preferred over 33 and 8 is preferred over 24.
Store all found factors in an array. The array would contain digits in non-increasing order, so finally print the array in reverse order.
Following is the implementation of above concept.
C++
#include<bits/stdc++.h> using namespace std; // Maximum number of digits in output #define MAX 50 // prints the smallest number // whose digits multiply to n void findSmallest( int n) { int i, j = 0; // To store digits of result // in reverse order int res[MAX]; // Case 1: If number is smaller than 10 if (n < 10) { cout << n + 10; return ; } // Case 2: Start with 9 and // try every possible digit for (i = 9; i > 1; i--) { // If current digit divides n, then store all // occurrences of current digit in res while (n % i == 0) { n = n / i; res[j] = i; j++; } } // If n could not be broken // in form of digits (prime factors // of n are greater than 9) if (n > 10) { cout << "Not possible" ; return ; } // Print the result array in reverse order for (i = j - 1; i >= 0; i--) cout << res[i]; } // Driver Code int main() { findSmallest(7); cout << "\n" ; findSmallest(36); cout << "\n" ; findSmallest(13); cout << "\n" ; findSmallest(100); return 0; } // This code is contributed by Code_Mech |
C
#include<stdio.h> // Maximum number of digits in output #define MAX 50 // prints the smallest number whose digits multiply to n void findSmallest( int n) { int i, j=0; int res[MAX]; // To store digits of result in reverse order // Case 1: If number is smaller than 10 if (n < 10) { printf ( "%d" , n+10); return ; } // Case 2: Start with 9 and try every possible digit for (i=9; i>1; i--) { // If current digit divides n, then store all // occurrences of current digit in res while (n%i == 0) { n = n/i; res[j] = i; j++; } } // If n could not be broken in form of digits (prime factors of n // are greater than 9) if (n > 10) { printf ( "Not possible" ); return ; } // Print the result array in reverse order for (i=j-1; i>=0; i--) printf ( "%d" , res[i]); } // Driver program to test above function int main() { findSmallest(7); printf ( "\n" ); findSmallest(36); printf ( "\n" ); findSmallest(13); printf ( "\n" ); findSmallest(100); return 0; } |
Java
// Java program to find the smallest number whose // digits multiply to a given number n import java.io.*; class Smallest { // Function to prints the smallest number whose // digits multiply to n static void findSmallest( int n) { int i, j= 0 ; int MAX = 50 ; // To store digits of result in reverse order int [] res = new int [MAX]; // Case 1: If number is smaller than 10 if (n < 10 ) { System.out.println(n+ 10 ); return ; } // Case 2: Start with 9 and try every possible digit for (i= 9 ; i> 1 ; i--) { // If current digit divides n, then store all // occurrences of current digit in res while (n%i == 0 ) { n = n/i; res[j] = i; j++; } } // If n could not be broken in form of digits (prime factors of n // are greater than 9) if (n > 10 ) { System.out.println( "Not possible" ); return ; } // Print the result array in reverse order for (i=j- 1 ; i>= 0 ; i--) System.out.print(res[i]); System.out.println(); } // Driver program public static void main (String[] args) { findSmallest( 7 ); findSmallest( 36 ); findSmallest( 13 ); findSmallest( 100 ); } } // Contributed by Pramod Kumar |
Python3
# Python code to find the smallest number # whose digits multiply to give n # function to print the smallest number whose # digits multiply to n def findSmallest(n): # Case 1 - If the number is smaller than 10 if n < 10 : print (n + 10 ) return # Case 2 - Start with 9 and try every possible digit res = [] # to sort digits for i in range ( 9 , 1 , - 1 ): # If current digit divides n, then store all # occurrences of current digit in res while n % i = = 0 : n = n / i res.append(i) # If n could not be broken in the form of digits # prime factors of n are greater than 9 if n > 10 : print ( "Not Possible" ) return # Print the number from result array in reverse order n = res[ len (res) - 1 ] for i in range ( len (res) - 2 , - 1 , - 1 ): n = 10 * n + res[i] print (n) # Driver Code findSmallest( 7 ) findSmallest( 36 ) findSmallest( 13 ) findSmallest( 100 ) # This code is contributed by Harshit Agrawal |
C#
// C# program to find the smallest number whose // digits multiply to a given number n using System; class GFG { // Function to prints the smallest number // whose digits multiply to n static void findSmallest( int n) { int i, j=0; int MAX = 50; // To store digits of result in // reverse order int []res = new int [MAX]; // Case 1: If number is smaller than 10 if (n < 10) { Console.WriteLine(n + 10); return ; } // Case 2: Start with 9 and try every // possible digit for (i = 9; i > 1; i--) { // If current digit divides n, then // store all occurrences of current // digit in res while (n % i == 0) { n = n / i; res[j] = i; j++; } } // If n could not be broken in form of // digits (prime factors of n // are greater than 9) if (n > 10) { Console.WriteLine( "Not possible" ); return ; } // Print the result array in reverse order for (i = j-1; i >= 0; i--) Console.Write(res[i]); Console.WriteLine(); } // Driver program public static void Main () { findSmallest(7); findSmallest(36); findSmallest(13); findSmallest(100); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find the // smallest number whose // digits multiply to a // given number n prints the // smallest number whose digits // multiply to n function findSmallest( $n ) { // To store digits of // result in reverse order $i ; $j = 0; $res ; // Case 1: If number is // smaller than 10 if ( $n < 10) { echo $n + 10; return ; } // Case 2: Start with 9 and // try every possible digit for ( $i = 9; $i > 1; $i --) { // If current digit divides // n, then store all // occurrences of current // digit in res while ( $n % $i == 0) { $n = $n / $i ; $res [ $j ] = $i ; $j ++; } } // If n could not be broken // in form of digits // (prime factors of n // are greater than 9) if ( $n > 10) { echo "Not possible" ; return ; } // Print the result // array in reverse order for ( $i = $j - 1; $i >= 0; $i --) echo $res [ $i ]; } // Driver Code findSmallest(7); echo "\n" ; findSmallest(36); echo "\n" ; findSmallest(13); echo "\n" ; findSmallest(100); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to find the smallest number whose // digits multiply to a given number n // Maximum number of digits in output // prints the smallest number // whose digits multiply to n function findSmallest(n) { let i, j = 0; // To store digits of result // in reverse order let res = new Array(50); // Case 1: If number is smaller than 10 if (n < 10) { document.write(n + 10); return ; } // Case 2: Start with 9 and // try every possible digit for (i = 9; i > 1; i--) { // If current digit divides n, then store all // occurrences of current digit in res while (n % i == 0) { n = Math.floor(n / i); res[j] = i; j++; } } // If n could not be broken // in form of digits (prime factors // of n are greater than 9) if (n > 10) { document.write( "Not possible" ); return ; } // Print the result array in reverse order for (i = j - 1; i >= 0; i--) document.write(res[i]); } // Driver Code findSmallest(7); document.write( "<br>" ); findSmallest(36); document.write( "<br>" ); findSmallest(13); document.write( "<br>" ); findSmallest(100); // This code is contributed by Mayank Tyagi </script> |
Output:
17 49 Not possible 455
Time Complexity: O(log2n * 10)
Auxiliary Space: O(MAX)
Contact Us