#2698

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Find the Punishment Number of an Integer

Find the punishment number of a given integer using backtracking search with pruning.

Problem Statement

Given a positive integer n, you are tasked with finding the punishment number of n. The punishment number is defined as the sum of squares of all integers i within the range [1, n] that satisfy a specific condition. The condition is that the square of i must be partitioned in such a way that the sum of the resulting digits equals i itself.

For example, for n = 10, the punishment number is 182. The valid integers i in the range [1, 10] are 1, 9, and 10, as their squares can be split into digits whose sum matches i. The sum of their squares (1 + 81 + 100) gives the punishment number.

Examples

Example 1

Input: n = 10

Output: 182

There are exactly 3 integers i in the range [1, 10] that satisfy the conditions in the statement:

1 since 1 * 1 = 1
9 since 9 * 9 = 81 and 81 can be partitioned into 8 and 1 with a sum equal to 8 + 1 == 9.
10 since 10 * 10 = 100 and 100 can be partitioned into 10 and 0 with a sum equal to 10 + 0 == 10. Hence, the punishment number of 10 is 1 + 81 + 100 = 182

Example 2

Input: n = 37

Output: 1478

There are exactly 4 integers i in the range [1, 37] that satisfy the conditions in the statement:

1 since 1 * 1 = 1.
9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6. Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478

Constraints

1 <= n <= 1000

Solution Approach

Backtracking Search with Pruning

A backtracking approach is used to explore all integers i in the range [1, n]. For each i, check if its square can be partitioned into digits that sum to i. Use pruning to eliminate unnecessary branches where the partitioning fails.

Digit Partitioning

For each square, partition it into all possible digit combinations. Check if the sum of the digits equals the original integer i. This is the key condition for including i in the punishment number sum.

Efficient Checking with Constraints

To optimize, avoid recalculating for the same integers and skip over unnecessary checks using constraints. This ensures the algorithm performs efficiently within the given bounds (1 <= n <= 1000).

Complexity Analysis

Metric	Value
Time	O(n \cdot 2^{\log_{10}(n)})
Space	O({\log_{10}(n)})

The time complexity of this solution is O(n * 2^{log_{10}(n)}) due to the backtracking exploration of possible partitions for each square. The space complexity is O(log_{10}(n)) as we store the partitioned digits in a recursive call stack.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration + DFS

We enumerate $i$, where $1 \leq i \leq n$. For each $i$, we split the decimal representation string of $x = i^2$, and then check whether it meets the requirements of the problem. If it does, we add $x$ to the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

Continue Practicing

#2597 the number of beautiful subsets #2178 maximum split of positive even integers #2048 next greater numerically balanced number