> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find the Punishment Number of an Integer

> Tested Python solution for LeetCode 2698 with 23 pytest cases. Generate a practice environment with lcpy.

LeetCode 2698, [Medium](/catalog/medium). Topics: [Math](/catalog/topics/math), [Backtracking](/catalog/topics/backtracking). [View on LeetCode](https://leetcode.com/problems/find-the-punishment-number-of-an-integer/description/).

Generate this problem as a practice environment: tested reference solution, 23 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2698   # by problem number
lcpy gen -s find_the_punishment_number_of_an_integer   # by problem name
```

## Problem

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 <= n`
* The decimal representation of `i * i` can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals `i`.

### Examples

```
Input: n = 10
Output: 182
Explanation: 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
```

```
Input: n = 37
Output: 1478
Explanation: 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

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_punishment_number_of_an_integer/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_punishment_number_of_an_integer/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n * d^2) where d is the digit count of i*i (partition search per i)
    # Space: O(d) recursion depth
    def punishment_number(self, n: int) -> int:
        def can_partition(sq: str, target: int, idx: int = 0, cur: int = 0) -> bool:
            if idx == len(sq):
                return cur == target
            for j in range(idx + 1, len(sq) + 1):
                part = int(sq[idx:j])
                if cur + part > target:
                    break
                if can_partition(sq, target, j, cur + part):
                    return True
            return False

        total = 0
        for i in range(1, n + 1):
            if can_partition(str(i * i), i):
                total += i * i
        return total
```

## Complexity

| Time | Space |
| - | - |
| O(n \* d^2) where d is the digit count of i\*i (partition search per i) | O(d) recursion depth |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.