Problem statement

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

Solution

In this problem we need to find number of solutions of x**i + y**j <= bound with given x, y, bound. What we can do is just check all possible solutions: in fact there will be not a lot of different solutions, we discuss it in complexity section. Here what we do is to generate all possible powers of x and y, which are smaller than bound and check all pairs. Be careful with case x = 1 or y = 1 to avoid infinite loop.

Complexity

There will be O(log_x(bound)) = O(log(bound)) options to choose power of x, and in the same way there will be O(log_y(bound)) = O(log(bound)) options for power of y. So, it total, there will be O(log^2(bound)) pairs which we check, which is not very big number. Space complexity is the same.

Code

class Solution:
    def powerfulIntegers(self, x, y, bound):
        pow_x, pow_y = [1], [1]
        while pow_x[-1]*x < bound and x > 1: pow_x.append(pow_x[-1]*x)
        while pow_y[-1]*y < bound and y > 1: pow_y.append(pow_y[-1]*y)
        return {i+j for i, j in product(pow_x, pow_y) if i + j <= bound}