[Leetcode] Minimum Factorization, Solution

Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a.

If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.

Example 1
Input:

48 

Output:

68

Example 2
Input:

15

Output:

35

[Thoughts]

一道实现题。把因子从9开始往下除，直到a为1为止。中间需要加一些溢出检测来处理特殊case。



[Code]

1:    int smallestFactorization(int a) {  
2:      if(a == 1) return 1;  
3:      long res = 0;  
4:        
5:      int factor = 9;  
6:      int rotation = 1;  
7:      int bit = 0;  
8:      while(a > 1 && factor > 1) {  
9:          
10:        if(a % factor != 0) {  
11:          factor --;  
12:          continue;  
13:        }  
14:          
15:        a = a/factor;  
16:        res = factor* rotation + res;  
17:        rotation *= 10;  
18:        bit ++;  
19:        //32bit integer不会超过9个数字，这里检测溢出  
20:        if(bit > 9) return 0;  
21:         
22:      }  
23:        
24:      if(factor == 1) return 0;  
25:      return (int)res;  
26:    }