625. Minimum Factorization
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.
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int smallestFactorization(int a) {
if(a < 10)
return a;
int digit = 9;
long res = 0, mul = 1;
while(digit > 1) {
while(!(a % digit)) {
a/=digit;
res += mul * digit;
mul = (mul<<3) + (mul<<1);
if(res > INT_MAX)
return 0;
}
digit--;
}
return a == 1 ? res : 0;
}
};
|
