Given a positive integer n, return the punishment number of n.
The punishment number of n is defined as the sum of the squares of all integers i such that:
1 <= i <= ni * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.Example 1:
Input: n = 10 Output: 182 Explanation: There are exactly 3 integers i 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. Hence, the punishment number of 10 is 1 + 81 + 100 = 182
Example 2:
Input: n = 37 Output: 1478 Explanation: There are exactly 4 integers i 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 <= 1000In #2698 Find the Punishment Number of an Integer, the goal is to compute the sum of i * i for all integers 1 ≤ i ≤ n where the decimal representation of i² can be partitioned into contiguous substrings whose numeric sum equals i. The key idea is to check each candidate number and verify whether its square satisfies this partition rule.
A practical approach is to compute sq = i * i and treat it as a string. Then use backtracking to try every possible way of splitting the digits into substrings. During recursion, accumulate the numeric values of chosen substrings and stop early if the running sum exceeds i. If a partition exactly sums to i, the number contributes i² to the punishment number.
Since the length of i² is small, exploring all partitions is manageable. This method combines string partitioning and pruning to efficiently validate each number. The final result is obtained by summing valid squares.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking over partitions of i² | O(n * 2^d) | O(d) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Can we generate all possible partitions of a number?
Use a recursive algorithm that splits the number into two parts, generates all possible partitions of each part recursively, and then combines them in all possible ways.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Backtracking is used because the digits of i² can be split in many different ways. The algorithm explores each possible partition and checks whether the resulting numbers add up to i, stopping early when the sum becomes too large.
Problems involving digit partitioning and backtracking patterns appear in many technical interviews. While this exact problem may vary, the underlying concepts of recursion, pruning, and combinational exploration are commonly tested.
The solution mainly relies on recursion and string processing. Converting i² into a string allows easy digit partitioning, while recursion or DFS helps explore all possible substring splits.
The common approach is to iterate from 1 to n, compute i², and use backtracking to check if its digits can be partitioned into numbers that sum to i. Pruning branches where the partial sum exceeds the target helps keep the recursion efficient.