Every day a Leetcode
题目来源:3345. 最小可整除数位乘积 I
解法1:枚举
至多循环 10 次,一定会遇到个位数为 0 的数字,数位乘积是 0,一定是 t 的倍数。
所以暴力枚举即可。
代码:
/** @lc app=leetcode.cn id=3345 lang=cpp** [3345] 最小可整除数位乘积 I*/// @lc code=start
class Solution
{
public:int smallestNumber(int n, int t){for (int i = n; i <= n + 10; i++)if (digitMultSum(i) % t == 0)return i;return -1;}// 辅函数 - 求数字 x 的各数位之积int digitMultSum(int x){int res = 1;while (x){res *= (x % 10);x /= 10;}return res;}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(logn)。
空间复杂度:O(1)。