-
Notifications
You must be signed in to change notification settings - Fork 0
/
625. 最小因式分解.cpp
57 lines (48 loc) · 1.19 KB
/
625. 最小因式分解.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
问题描述:
给定一个正整数 a,找出最小的正整数 b 使得 b 的所有数位相乘恰好等于 a。
如果不存在这样的结果或者结果不是 32 位有符号整数,返回 0。
样例 1
输入:
48
输出:
68
样例 2
输入:
15
输出:
35
问题分析:
注意,结果超过32位的情况。
*/
class Solution {
public:
int smallestFactorization(int a) {
vector<int> res;
bool canDivide = helper(res,a);
if ( !canDivide ) return 0;
return f(res);
}
bool helper( vector<int>& res, int a ){
int i;
if ( a<10 ){
res.push_back(a);
return true;
}
for ( i=9; i>1; --i )
if ( a%i==0 ){
res.push_back( i );
return helper( res, a/i );
}
return false;
}
int f( vector<int>& res ){
sort(res.begin(), res.end());
long i = 0;
for (auto e:res){
i = i*10 + e;
if ( i>INT_MAX ) return 0;
}
return i;
}
};