原文链接: https://leetcode-cn.com/problems/powerful-integers

英文原文

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as xi + yj for some integers i >= 0 and j >= 0.

You may return the answer in any order. In your answer, each value should occur at most once.

 

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

 

Constraints:

• 1 <= x, y <= 100
• 0 <= bound <= 106

中文题目

给定两个正整数 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

通过代码

官方题解

方法：暴力法

思路

如果 $x^i > \text{bound}$，那么 $x^i + y^j$ 也不可能小于等于 bound。 对于 $y^j$ 也是同样的道理。

因此，我们只需要对于所有的 $0 \leq i, j \leq \log_x(\text{bound}) < 18$ 生成一遍答案就行了。

我们可以用一个 HashSet 来存储所有不同的答案。

[AV4vVh9p-Java]
class Solution { 
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> seen = new HashSet();
        for (int i = 0; i < 18 && Math.pow(x, i) <= bound; ++i)
            for (int j = 0; j < 18 && Math.pow(y, j) <= bound; ++j) {
                int v = (int) Math.pow(x, i) + (int) Math.pow(y, j);
                if (v <= bound)
                    seen.add(v);
            }

        return new ArrayList(seen);
    }
}

[AV4vVh9p-Python]
class Solution(object): 
    def powerfulIntegers(self, x, y, bound):
        ans = set()
        # 2**18 > bound
        for i in xrange(18):
            for j in xrange(18):
                v = x**i + y**j
                if v <= bound:
                    ans.add(v)
        return list(ans)

复杂度分析

• 时间复杂度：$O(\log^2{\text{bound}})$。

• 空间复杂度：$O(\log^2{\text{bound}})$。

统计信息

通过次数	提交次数	AC比率
11377	27541	41.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言