Skip to content

970. Powerful Integers

Description

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as xi + yj for some integers i >= 0 and j >= 0.

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 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

 

Constraints:

  • 1 <= x, y <= 100
  • 0 <= bound <= 106

Solutions

Solution 1: Hash Table + Enumeration

According to the description of the problem, a powerful integer can be represented as \(x^i + y^j\), where \(i \geq 0\), \(j \geq 0\).

The problem requires us to find all powerful integers that do not exceed \(bound\). We notice that the value range of \(bound\) does not exceed \(10^6\), and \(2^{20} = 1048576 \gt 10^6\). Therefore, if \(x \geq 2\), then \(i\) is at most \(20\) to make \(x^i + y^j \leq bound\) hold. Similarly, if \(y \geq 2\), then \(j\) is at most \(20\).

Therefore, we can use double loop to enumerate all possible \(x^i\) and \(y^j\), denoted as \(a\) and \(b\) respectively, and ensure that \(a + b \leq bound\), then \(a + b\) is a powerful integer. We use a hash table to store all powerful integers that meet the conditions, and finally convert all elements in the hash table into the answer list and return it.

Note that if \(x=1\) or \(y=1\), then the value of \(a\) or \(b\) is always equal to \(1\), and the corresponding loop only needs to be executed once to exit.

The time complexity is \(O(\log^2 bound)\), and the space complexity is \(O(\log^2 bound)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        ans = set()
        a = 1
        while a <= bound:
            b = 1
            while a + b <= bound:
                ans.add(a + b)
                b *= y
                if y == 1:
                    break
            if x == 1:
                break
            a *= x
        return list(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> ans = new HashSet<>();
        for (int a = 1; a <= bound; a *= x) {
            for (int b = 1; a + b <= bound; b *= y) {
                ans.add(a + b);
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }
        return new ArrayList<>(ans);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> ans;
        for (int a = 1; a <= bound; a *= x) {
            for (int b = 1; a + b <= bound; b *= y) {
                ans.insert(a + b);
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }
        return vector<int>(ans.begin(), ans.end());
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func powerfulIntegers(x int, y int, bound int) (ans []int) {
    s := map[int]struct{}{}
    for a := 1; a <= bound; a *= x {
        for b := 1; a+b <= bound; b *= y {
            s[a+b] = struct{}{}
            if y == 1 {
                break
            }
        }
        if x == 1 {
            break
        }
    }
    for x := range s {
        ans = append(ans, x)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function powerfulIntegers(x: number, y: number, bound: number): number[] {
    const ans = new Set<number>();
    for (let a = 1; a <= bound; a *= x) {
        for (let b = 1; a + b <= bound; b *= y) {
            ans.add(a + b);
            if (y === 1) {
                break;
            }
        }
        if (x === 1) {
            break;
        }
    }
    return Array.from(ans);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} x
 * @param {number} y
 * @param {number} bound
 * @return {number[]}
 */
var powerfulIntegers = function (x, y, bound) {
    const ans = new Set();
    for (let a = 1; a <= bound; a *= x) {
        for (let b = 1; a + b <= bound; b *= y) {
            ans.add(a + b);
            if (y === 1) {
                break;
            }
        }
        if (x === 1) {
            break;
        }
    }
    return [...ans];
};

Comments