PROBLEM LINKS:
Author: Animesh Fatehpuria
Testers: Rajat De Sumit Shyamsukha
Editorialist: Animesh Fatehpuria
DIFFICULTY:
EASY
PREREQUISITES:
Factorization,Greedy
PROBLEM:
Given a Number N print the smallest possible number X such that product of digits of X is equal to N.
If no such number exists, print -1.
EXPLANATION:
For a given N, The two cases to be considered are:
Case 1: N < 10 : When N is smaller than 10, the output is always N+10. For example for N = 6, output is 16. For N = 8, output is 18.
Case 2: N >= 10 : Find all factors of N which are between 2 and 9 (both inclusive).
The main idea is to start searching from 9 and move towards 2 so that the number of digits in the result are minimized. For Example 9 is preferred over 33 and 8 is preferred over 24.
The Idea is to store all found factors in an array. The array would contain digits in decreasing order, so finally print the array in reverse order.
Here is the PseudoCode :
// We 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 Array
while (N%i==0)
{
Divide N by i
Store i in Array
}
}
// If N could not be broken in form of digits (prime factors of N are greater than 9)
if(N> 10)
{
print -1
}
else
{
Print Array in ReverseOrder
}
For 30 Points : If you don’t use Arrays and try to build the number or Brute-Force using a for Loop from 1 to N, you fail for cases when N<=10^16 .
For 100 Points: The above logic applies.