给定两个正整数 x
和 y
,如果某一整数等于 x^i + y^j
,其中整数 i >= 0
且 j >= 0
,那么我们认为该整数是一个强整数。
返回值小于或等于 bound
的所有强整数组成的列表。
你可以按任何顺序返回答案。在你的回答中,每个值最多出现一次。
示例 1:
输入:x = 2, y = 3, bound = 10 输出:[2,3,4,5,7,9,10] 解释: 2 = 2^0 + 3^0 3 = 2^1 + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 + 3^2
示例 2:
输入:x = 3, y = 5, bound = 15 输出:[2,4,6,8,10,14]
提示:
1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6
题目标签:Hash Table / Math
题目链接:LeetCode / LeetCode中国
Language | Runtime | Memory |
---|---|---|
cpp | 8 ms | 1.2 MB |
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
set<int> us;
for (int i=0; x==1 ? i<1 : pow(x, i) < bound; ++i) {
for (int j=0; y==1 ? j<1 : pow(y, j) < bound; ++j) {
int z = pow(x, i) + pow(y, j);
if (z <= bound) {
us.insert(z);
}
}
}
vector<int> res;
for (int i : us) {
res.push_back(i);
}
return res;
}
};