What is the punishment number of an integer?

The punishment number is the sum of the squares of integers i in the range [1, n] that satisfy the condition where the sum of the digits of i^2 equals i.

How do you efficiently solve the punishment number problem?

You can use backtracking with pruning to explore valid integer candidates and check their square partitions for digit sums.

What is the time complexity of the punishment number problem?

The time complexity is O(n * 2^{log_{10}(n)}) due to backtracking and partition checking.

What are the key pitfalls in solving the punishment number problem?

Common pitfalls include failing to partition squares correctly, not implementing pruning, and inefficient handling of large inputs.

What pattern does the punishment number problem follow?

The problem follows a backtracking search with pruning pattern, where you explore valid partitions and optimize the search space.

#2698

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

求一个整数的惩罚数

给你一个正整数 n ，请你返回 n 的惩罚数。 n 的惩罚数定义为所有满足以下条件 i 的数的平方和： 1 i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。示例 1：输入： n = 10 输出： 182 解释：总共有 3 个范围在 …

数学回溯

题目描述

给你一个正整数 n ，请你返回 n 的 惩罚数 。

n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：

1 <= i <= n
i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。

示例 1：

输入：n = 10
输出：182
解释：总共有 3 个范围在 [1, 10] 的整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
因此，10 的惩罚数为 1 + 81 + 100 = 182

示例 2：

输入：n = 37
输出：1478
解释：总共有 4 个范围在 [1, 37] 的整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
- 36 ，因为 36 * 36 = 1296 ，且 1296 可以分割成 1 + 29 + 6 。
因此，37 的惩罚数为 1 + 81 + 100 + 1296 = 1478

提示：

1 <= n <= 1000

lightbulb

解题思路

方法一：枚举 + DFS

我们枚举 $i$ ，其中 $1 \leq i \leq n$ ，对于每个 $i$ ，我们将 $x = i^2$ 的十进制表示的字符串进行分割，然后判断是否满足题目要求。如果满足，我们就将 $x$ 累加到答案中。

枚举结束，返回答案即可。

时间复杂度 $O(n^{1 + 2 \log_{10}^2})$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为给定的正整数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def check(s: str, i: int, x: int) -> bool:
            m = len(s)
            if i >= m:
                return x == 0
            y = 0
            for j in range(i, m):
                y = y * 10 + int(s[j])
                if y > x:
                    break
                if check(s, j + 1, x - y):
                    return True
            return False

        ans = 0
        for i in range(1, n + 1):
            x = i * i
            if check(str(x), 0, i):
                ans += x
        return ans

speed

复杂度分析

指标	值
时间	O(n \cdot 2^{\log_{10}(n)})
空间	O({\log_{10}(n)})

psychology

面试官常问的追问

外企场景

question_mark
Assess how well the candidate handles backtracking and partitioning problems.
question_mark
Evaluate if the candidate can optimize the search using pruning techniques.
question_mark
Check if the candidate understands the digit partitioning requirement and how to check it efficiently.

warning

常见陷阱

外企场景

error
Failing to properly partition the square of i and check the digit sum.
error
Not implementing pruning, leading to inefficient solutions for larger n.
error
Overlooking constraints and trying to solve for larger values of n without optimization.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow n to be larger (e.g., up to 10000), requiring more efficient partitioning checks.
arrow_right_alt
Allow non-positive integers as input, modifying the conditions accordingly.
arrow_right_alt
Implement the problem using dynamic programming to reduce redundant calculations.

help

常见问题

外企场景

继续练习

#2597 美丽子集的数目 #2178 拆分成最多数目的正偶数之和 #2048 下一个更大的数值平衡数