TopCoder problem "ProductOfDigits" used in SRM 424 (Division I Level One , Division II Level Two)



Problem Statement

    You are given an int N. Find the smallest positive integer X such that the product of its digits (in decimal notation) is equal to N. Return the number of digits in X, or return -1 if such a number does not exist.
 

Definition

    
Class:ProductOfDigits
Method:smallestNumber
Parameters:int
Returns:int
Method signature:int smallestNumber(int N)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
1
Returns: 1
Just take X = 1. It contains 1 digit.
1)
    
10
Returns: 2
Here the smallest possible X is 25.
2)
    
26
Returns: -1
3)
    
100
Returns: 3
The number 455 has 3 digits and the product of its digits is 4 * 5 * 5 = 100.
4)
    
2520
Returns: 4
5)
    
864
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10177

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13515&pm=10177

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simple Math