970.md

970. Powerful Integers

Solution 1 (O(log(bound)^2))

class Solution(object):
    def powerfulIntegers(self, x, y, bound):
        """
        :type x: int
        :type y: int
        :type bound: int
        :rtype: List[int]
        """
        x_list = []
        y_list = []
        if x == 1:
            if bound > 1:
                x_list = [1]
        else:
            cur = 1
            while cur < bound:
                x_list.append(cur)
                cur = cur * x
        if y == 1:
            if bound > 1:
                y_list = [1]
        else:
            cur = 1
            while cur < bound:
                y_list.append(cur)
                cur = cur * y
        ans = []
        for cur_x in x_list:
            for cur_y in y_list:
                cur_ans = cur_x + cur_y
                if cur_ans <= bound:
                    ans.append(cur_x + cur_y)
                else:
                    break
        ans = list(set(ans))
        return ans