[LeetCode] 970. Powerful Integers

[grandyang]

Given two positive integers x and y, an integer is  powerful  if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all  powerful  integers that have value less than or equal to bound.

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 = 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

Example 2:

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

Note:

• 1 <= x <= 100
• 1 <= y <= 100
• 0 <= bound <= 10^6

这道题定义了一种强力整数，说是给定的整数x和y分别的i次幂和j次幂之和，现在又给了一个整数 bound，让返回不超过这个范围的所有的强力整数。既然是一道 Easy 的题目，就不要考虑太多的技巧了，直接上无脑破解了吧。博主最开始的解法是在 bound 范围内先分别生成x和y的指数数组，即 x^0, x^1, x^2.... 和 y^0, y^1, y^2....，然后从两个数组中各自任意取出一个数字来相加，只要不超过 bound，就可以放入结果 res 中了，需要注意的是，若x和y等于1的话，那么会陷入死循环，因为乘以1永远等于其本身，所以要加另外的判断。博主的方法其实可以优化一下，没有必要用额外的数组去保存，而是可以直接在 for 循环中处理就可以了。还有，为了防止重复数字，先是把结果都存入一个 TreeSet 中，利用其可以去除重复项的特点，最后再转回数组就行了，参见代码如下：

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        set<int> res;
        for (int a = 1; a < bound; a *= x) {
            for (int b = 1; a + b <= bound; b *= y) {
                res.insert(a + b);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return vector<int>(res.begin(), res.end());
    }
};

Github 同步地址:

#970

参考资料：

https://leetcode.com/problems/powerful-integers/

https://leetcode.com/problems/powerful-integers/discuss/214212/JavaC%2B%2BPython-Easy-Brute-Force

https://leetcode.com/problems/powerful-integers/discuss/214197/Java-straightforward-try-all-combinations

LeetCode All in One 题目讲解汇总(持续更新中...)