What defines a powerful integer in LeetCode problem 970?

A powerful integer is any number that can be expressed as x^i + y^j for non-negative integers i and j, not exceeding the given bound.

Why is a Hash Table required for Powerful Integers?

Using a Hash Table ensures each computed sum appears only once, preventing duplicates and satisfying the problem constraints.

How do you handle x or y equal to 1?

When x or y equals 1, the exponent loop must stop after the first iteration to avoid infinite repetition, since 1^i = 1 for all i.

What is the time complexity for generating powerful integers?

Time complexity is O(log_bound(x) * log_bound(y)) because loops iterate over powers only until the sum exceeds the bound.

Can the output be in any order?

Yes, the problem allows returning powerful integers in any order as long as each number appears at most once.

#970

Medium

auto_awesome哈希·数学

LeetCode 题解工作台

强整数

给定三个整数 x 、 y 和 bound ，返回值小于或等于 bound 的所有强整数组成的列表。如果某一整数可以表示为 x i + y j ，其中整数 i >= 0 且 j >= 0 ，那么我们认为该整数是一个强整数。你可以按任何顺序返回答案。在你的回答中，每个值最多出现一…

哈希表数学枚举

题目描述

给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。

如果某一整数可以表示为 xⁱ + y^j ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。

你可以按 任何顺序 返回答案。在你的回答中，每个值最多出现一次。

示例 1：

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
2 = 2⁰ + 3⁰
3 = 2¹ + 3⁰
4 = 2⁰ + 3¹
5 = 2¹ + 3¹
7 = 2² + 3¹
9 = 2³ + 3⁰
10 = 2⁰ + 3²

示例 2：

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

提示：

1 <= x, y <= 100
0 <= bound <= 10⁶

lightbulb

解题思路

方法一：哈希表 + 枚举

根据题目描述，一个强整数可以表示成 $x^i + y^j$ ，其中 $i \geq 0$ , $j \geq 0$ 。

题目需要我们找出所有不超过 $bound$ 的强整数，我们注意到 $bound$ 的取值范围不超过 $10^6$ ，而 $2^{20} = 1048576 \gt 10^6$ 。因此，如果 $x \geq 2$ ，那么 $i$ 最大不超过 $20$ ，才有可能使得 $x^i + y^j \leq bound$ 成立。同理，如果 $y \geq 2$ ，那么 $j$ 最大不超过 $20$ 。

因此我们可以使用双重循环，枚举所有可能的 $x^i$ 和 $y^j$ ，分别记为 $a$ 和 $b$ ，并保证 $a + b \leq bound$ ，此时 $a + b$ 即为一个强整数。我们使用哈希表存储所有满足条件的强整数，最后将哈希表中的所有元素转换成答案列表返回即可。

注意，如果 $x=1$ 或者 $y=1$ ，那么 $a$ 或者 $b$ 的值恒等于 $1$ ，对应的循环只需要执行一次即可退出。

时间复杂度 $O(\log^2 bound)$ ，空间复杂度 $O(\log^2 bound)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

speed

复杂度分析

指标	值
时间	complexity is O(log_bound(x) * log_bound(y)) because we iterate powers of x and y only until the bound is exceeded. Space complexity is O(N * M) where N and M are the number of powers of x and y that fit within the bound, required for storing sums in a Hash Set.
空间	O(N \times M)

psychology

面试官常问的追问

外企场景

question_mark
Focus on pruning loops as soon as x^i + y^j exceeds the bound.
question_mark
Ensure duplicate sums are not included, highlighting proper Hash Table usage.
question_mark
Expect clarification on why enumeration combined with mathematical stopping conditions is efficient.

warning

常见陷阱

外企场景

error
Failing to break loops early, leading to unnecessary computations and potential TLE.
error
Using a list instead of a Hash Set, which can allow duplicates in the output.
error
Incorrectly handling the edge case when x or y equals 1, which causes infinite loops if not properly stopped.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return powerful integers in sorted order instead of arbitrary order.
arrow_right_alt
Restrict i and j to a maximum exponent value instead of using bound.
arrow_right_alt
Compute sums modulo a number to avoid large integers and test modular properties.

help

常见问题

外企场景

继续练习

#869 重新排序得到 2 的幂 #963 最小面积矩形 II #957 N 天后的牢房