题目描述
给你一个三位数整数 n
。
如果经过以下修改得到的数字 恰好 包含数字 1
到 9
各一次且不包含任何 0
,那么我们称数字 n
是 迷人的:
- 将
n
与数字2 * n
和3 * n
连接。
如果 n
是迷人的,返回 true
,否则返回 false
。
连接 两个数字表示把它们首尾相接连在一起。比方说 121
和 371
连接得到 121371
。
样例
输入:n = 192
输出:true
解释:我们将数字 n = 192,2 * n = 384 和 3 * n = 576 连接,得到 192384576。
这个数字包含 1 到 9 恰好各一次。
输入:n = 100
输出:false
解释:我们将数字 n = 100,2 * n = 200 和 3 * n = 300 连接,得到 100200300。
这个数字不符合上述条件。
限制
100 <= n <= 999
算法
(模拟) $O(\log n)$
- 按照题目模拟,如果 $n \le 333$,则连接后的数字为 $n \cdot 1002003$。如果 $333 < n < 500$,则为 $n \cdot 10002003$;否则,最终数字为 $n \cdot 100020003$。
- 遍历数字的每一位,用二进制哈希表判断。
时间复杂度
- 数字共有 $O(\log n)$ 位,故时间复杂度为 $O(\log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
bool isFascinating(LL n) {
if (n <= 333) n *= 1002003;
else if (n < 500) n *= 10002003;
else n *= 100020003;
int seen = 1;
while (n > 0) {
if ((seen >> (n % 10)) & 1)
return false;
seen |= 1 << (n % 10);
n /= 10;
}
return true;
}
};