Friday, July 21, 2017

[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:    }  


No comments: