### 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.