C ++中的最小分解
假设我们有一个正整数x,我们必须找到最小的正整数b,每个数字的乘积等于x。如果我们没有这样的答案,则返回0。
因此,如果输入为48,则输出为68
为了解决这个问题,我们将遵循以下步骤-
ret:=0,mul:=1
如果<2,则:
返回一个
对于初始化i:=9,当i>=2时,更新(将i减1),请执行-
ret:=我*mul+ret
mul:=mul*10
a:=a/i
当modi等于0时,做-
返回(如果a<2并ret<inf,则退出,否则为0)
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int smallestFactorization(int a) { lli ret = 0; lli mul = 1; if (a < 2) return a; for (lli i = 9; i >= 2; i--) { while (a % i == 0) { ret = i * mul + ret; mul *= 10; a /= i; } } return a < 2 && ret < INT_MAX ? ret : 0; } }; main(){ Solution ob; cout << (ob.smallestFactorization(48)); }
输入值
48
输出结果
68