970. Powerful Integers.cpp

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










/*
If x^i > bound then sum x^i + y^j can't be less than or equal to the bound.
Similarly for y^j

Thus, we only have to check for 0 <= i, j <= logx(bound) < 20

bound <= 1000000
20 = ceil( log2(upper limit of bound))
*/




class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        set<int> ss;
        int limit=ceil(log2(1000000)); // given in constraint

        for(int i=0; i<limit && pow(x, i)<=bound; i++){
            for(int j=0; j<limit && pow(y, j)<=bound; j++){
                long long tmp =pow(x, i)+ pow(y, j);
                if(tmp<=bound) ss.insert(tmp);
            }
        }

        return vector<int>(ss.begin(), ss.end());
    }
};