Leetcode 970: Powerful Integers

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



Notes:

The example given above is somehow misleading. One way to solve this problem is scan from 0 to bound, and check each word can be write as required. Obviously this way is too slow, since its time complexity is O(N^2).

A different way to think about it is that there are not many values of x^i in the bound range; the same is to y^j. Thus, we can check all the possible sums from them, and save the ones that fit the requirement.

Some details:
a): when x = 1 or y = 1;
b): there should be no redundant in the result.

See the code below,

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int> res;
        set<int> st;
        for(int i=1; i<bound; i *= x) {
            for(int j=1; i+j<=bound; j *= y) {
                if(st.count(i+j)) continue;
                st.insert(i+j);
                res.push_back(i+j);
                if(y==1) break;
            }
            if(x==1) break;
        }
        return res;
    }
};