Leetcode 970 Powerful Integers

发表于 |

给定两个非负整数x,y，若一个整数能表示成 x^i + y^j (i>=0,j>=0)，我们就把这个数称为是”powerful”的。
给定一个上界bound和两个数x,y，返回所有小于等于bound的”powerful”数

Example 1:
Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]

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

Note:

  1. 1 <= x <= 100
  2. 1 <= y <= 100
  3. 0 <= bound <= 10^6

思路分析：
由于这道题的数据非常之小，我们完全可以使用暴力法来计算，让i,j分别从0到20中遍历，把所有的x^i + y^j计算出来，去除重复的数即可。（2^20 > 10^6）

提一句，即使x,y中有1也没关系，这个逻辑完全覆盖到这种情况，不用担心遍历到所有数。

1
2
3
4
5
6
7
8
9
class Solution(object):
    def powerfulIntegers(self, x, y, bound):
        res = set()
        for i in range(20):
            for j in range(20):
                val = x**i + y**j
                if val > bound: break
                res.add(val)
        return list(res)