[LeetCode]#970. Powerful Integers

Environment: Python 3.7

Key technique: .set, math log, while, .add

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]

Analysis:

This case have binary “bound” and we can use while to calculate sum.

Solution:

from math import log
class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        number=set()
        i=0
        while x**i<=bound and i<=log(bound)+1:
            j=0
            while j<=bound and y**j<=bound:
                sum=x**i+y**j
                if sum > bound:
                    break
                number.add(sum)
                j+=1
            i+=1
        return number

Submitted result:

Lesson learn:

I don’t consider bound might give 100000 and get Time limit Exceeded fail. Therefor, I add log(bound) to reduce computing time.

Reference:

https://blog.csdn.net/fuxuemingzhu/article/details/85933995